Matrix bzw. Labyrinth

  • Matrix bzw. Labyrinth

    Hi,

    da ich öfter in diesem Forum lese und ich nun ein Problem habe, welches ich nicht direkt lösen kann, hoffe ich das hier mir jemand helfen kann :) (Die Erwartungen sind hoch ;))

    Quellcode

    1. package matrix;
    3. public class Matrix {
    5. /** 4 rows and 7 columns **/
    6. private int [][] matrix = {
    7. {0,0,0,0,-1,0,0},
    8. {0,-1,0,0,0,0,0},
    9. {0,-1,0,0,0,-1,0},
    10. {0,0,-1,0,0,0,0},
    11. };
    13. private int startRow;
    14. private int startColumn;
    16. private int targetRow;
    17. private int targetColumn;
    19. public Matrix() {
    21. startRow = 0;
    22. startColumn = 0;
    24. targetRow = 3;
    25. targetColumn = 6;
    27. }
    29. public static void main(String[] args) {
    32. }
    34. }
    Alles anzeigen


    Ich hab diese Matrix und möchte von einem Punkt A zu einem Punkt B.
    Die int Werte bedeuten:
    0 = Hier darf man gehn, Schritt erlaubt
    -1 = Hinternis d.h. hier kann man nicht gehn, kein Schritt erlaubt

    Ein Schritt der erlaubt war soll mit 1 in das entsprechende Matrixfeld eingetragen werden.

    Man kann von einem Feld nur in die vier Himmelsrichtungen laufen d.h. diagonal nicht.

    Ein gültiger Weg für diesen Code wäre z.B.

    Quellcode

    1. {1,1,1,1,-1,0,0},
    2. {0,-1,0,1,1,1,1},
    3. {0,-1,0,0,0,-1,1},
    4. {0,0,-1,0,0,0,1},


    Es geht nicht darum den kürzesten Weg zu finden sondern lediglich einen Weg.

    Viele Grüße und vielen Dank

  • Ich würde als erstes testen, ob ein direkter Nachbar betretbar (=1) ist.
    Das geht ja ganz einfach, indem du sagst :

    testeNachbar(feld){
    wenn array[x][y+1] == 1
    dann betretbarVertikal= true
    oder wenn array[x+1][y] == 1
    dann betretbarHorizontale = true
    }

    setze zeiger aufs neue Feld, wenn betretbarHorizontale / -Vertikal
    testeNachbar(neues feld)
    wenn testNachbar == false,
    setzte zeiger aufs vorherige Feld


    im Prinzip musst du nur den bisherigen Pfad in einem Array speichern und kannst so Problemlos wieder zurück.
    Es gibt sicherlich noch andere Techniken (Graphentheorie oder so), aber mir gefällt das Backtracking ganz gut ;)

    ciao