2017-10-06 4 views
0

Also habe ich eine 2D-Matrix, und ich soll den Pfad aufzeichnen, der die minimalen Kosten ergibt. Ich kann nur nach unten oder nach rechts gehen. Beispiel:Den optimalen Gitterweg für minimale Kosten aufzeichnen

2 4 1 
3 7 6 
3 8 9 

Output: right right down down 

Mein Code gibt die falschen Antworten, aber ich bin nicht in der Lage, warum zu erkennen. Ich habe auch meinen Code unten angehängt:

public static List<String> optimalGridPath(int[][] grid) { 

    ArrayList<String> answers = new ArrayList<String>(); 
    //TODO 
    int gridRows = grid.length-1; 
    int gridColumns = grid[0].length-1; 

    int solutionGrid[][] = new int[gridRows+1][gridColumns+1]; 

    for (int i = 0; i <= gridRows; i++) { 
     for (int j = 0; j <= gridColumns; j++) { 
      if (i > 0 && j > 0) 
       solutionGrid[i][j] = grid[i][j] + 
         Math.min(solutionGrid[i-1][j], solutionGrid[i][j-1]); 
      else if (j == 0 && i == 0) 
       solutionGrid[i][j] = grid[i][j]; 
      else if (j > 0) 
       solutionGrid[i][j] = grid[i][j] + solutionGrid[i][j-1]; 
      else 
       solutionGrid[i][j] = grid[i][j] + solutionGrid[i-1][j]; 
     } 
    } 

    while (gridRows != 0 && gridColumns != 0) { 
     if (gridColumns == 0) { 
      answers.add("down"); 
      gridRows--; 
     } 
     else if (gridRows == 0) { 
      answers.add("right"); 
      gridColumns--; 
     } 
     else { 
      if (solutionGrid[gridRows][gridColumns-1] < 
        solutionGrid[gridRows-1][gridColumns]) { 
       answers.add("right"); 
       gridColumns--; 
      } 
      else { 
       answers.add("down"); 
       gridRows--; 
      } 
     } 
    } 

    return answers; 
} 

Antwort

1

Der erste Teil Ihrer Lösung scheint korrekt zu sein, aber der zweite Teil ist nicht korrekt.

Nach der Ausführung Ihrer verschachtelten for-Schleifen wird jede Position in Ihrem solutionGrid mit den Mindestkosten gefüllt, um zu dieser Position zu gelangen.

Um den Mindestkostenpfad vom Start bis zum Ziel festzulegen, sollten Sie am Ziel beginnen und sich nach links oder oben bewegen, bis Sie den Start erreichen. Sie sollten sich nach links bewegen, wenn die Position im Lösungsgitter links von der aktuellen Position kleiner ist als die Position im Lösungsgitter über Ihrer aktuellen Position.

Sie haben dies getan, aber anstatt zu deklarieren, dass der richtige Pfad sich nach links oder nach oben bewegen soll, erklären Sie, dass Sie sich nach rechts oder nach unten bewegen.

Da Ihre Antwortliste von Anfang an bestimmen sollte, wie Sie zum Ziel gelangen, ist Ihre Antwortliste korrekt, aber in umgekehrter Reihenfolge.

Fix Ihr Programm durch

der Verwendung Aufruf
answers.insert(0, "right") 

und

answers.insert(0, "down") 

stattdessen das "add" Verfahren - die bis zum Ende Ihrer Array-Liste anhängen wird.

+0

Es ist so dumm, den Fehler hier nicht zu erkennen ..... es funktioniert jetzt perfekt. Vielen Dank! –

Verwandte Themen