Ein m × n rechteckiger Array repräsentiert das Labyrinth und 0 und 1 repräsentieren die Wege bzw. Hindernisse im Labyrinth. Entwerfen Sie ein Programm, um einen Pfad vom Eingang zum Ausgang für ein Einstellungslabyrinth zu finden, oder ziehen Sie die Schlussfolgerung, dass es keinen Weg gibt.
(1) Ausgabe des Labyrinth-Diagramms gemäß dem zweidimensionalen Array.
.
Beispiel:
Die obere linke Ecke (1, 1) ist der Eingang und die untere rechte Ecke (8, 9) ist der Ausgang.
Sie können die Backtracking -Methode verwenden, dh vom Eingang und Erkundung in eine bestimmte Richtung. Wenn dies erledigt werden kann, gehen Sie weiter vorwärts; Andernfalls ziehen Sie sich entlang des ursprünglichen Pfades zurück, erkunden Sie weiter in eine andere Richtung bis zur Ausgangsposition und finden Sie einen Pfad. Wenn alle möglichen Pfade untersucht werden und der Ausgang nicht erreicht wird, hat der Labyrinth -Satz keine Wege.
import Java.util.*; Klasse Position {public Position () {} public Position (int row, int col) {this.col = col; this.row = row; } public String toString () {return "(" + row + "," + col + ")"; } int row; int col;} class Maze {public Maze () {Maze = new int [15] [15]; stack = new Stack <POSPOME> (); p = neuer Boolescher [15] [15]; } /** Maze konstruieren* / public void init () {scanner scanner = neuer scanner (System.in); System.out.println ("Bitte geben Sie die Anzahl der Zeilen des Labyrinths ein); row = scanner.nextint (); System.out.println ("Bitte geben Sie die Anzahl der Spalten des Labyrinths ein); col = scanner.nextint (); System.out.println ("Bitte geben Sie" + Row + "Zeile" + col + "Spaltenlabyrinth"); int temp = 0; für (int i = 0; i <row; ++ i) {für (int j = 0; j <col; ++ j) {temp = scanner.NextInt (); Maze [i] [j] = temp; p [i] [j] = falsch; }}} /** Gehen Sie zurück zum Labyrinth, um festzustellen, ob es einen Ausweg gibt für (int i = 0; i <row +2; ++ i) {für (int j = 0; j <col +2; ++ j) {temp [0] [j] = 1; temp [Zeile + 1] [j] = 1; temp [i] [0] = temp [i] [col + 1] = 1; }} // das ursprüngliche Labyrinth in das neue Labyrinth für (int i = 0; i <row; ++ i) {für (int j = 0; j <col; ++ j) {temp [i +1] [j +1] = Maze [i] [j]; }} // starten Sie im Uhrzeigersinn von der oberen linken Ecke int i = 1; int j = 1; p [i] [j] = wahr; stack.push (neue Position (i, j)); while (! stack.empty () && (! (i == (row) && (j == col))))) {if ((temp [i] [j + 1] == 0) && (p [i] [j + 1] == false) {p [i] [j + 1] = true; stack.push (neue Position (i, j + 1)); J ++; } else if ((temp [i + 1] [j] == 0) && (p [i + 1] [j] == false)) {p [i + 1] [j] = true; stack.push (neue Position (i + 1, j)); i ++; } else if ((temp [i] [j - 1] == 0) && (p [i] [j - 1] == false)) {p [i] [j - 1] = true; stack.push (neue Position (i, j - 1)); J--; } else if ((temp [i - 1] [j] == 0) && (p [i - 1] [j] == false)) {p [i - 1] [j] = true; stack.push (neue Position (i - 1, j)); ich--; } else {stack.pop (); if (stack.empty ()) {break; } i = stack.peek (). row; j = stack.peek (). col; }} Stack <position> newpos = new stack <position> (); if (stack.empty ()) {break; } i = stack.peek (). row; j = stack.peek (). col; }} Stack <position> newpos = new stack <position> (); if (stack.empty ()) {System.out.println ("no path"); } else {System.out.println ("Es gibt Pfad"); System.out.println ("Der Pfad ist wie folgt:"); while (! stack.empty ()) {Position pos = new Position (); pos = stack.pop (); newpos.push (pos); }} / * * Grafischer Ausgangspfad * * / String -Ergebnis [] [] = new String [Zeile+1] [col+1]; für (int k = 0; k <row; ++ k) {für (int t = 0; t <col; ++ t) {result [k] [t] = (Maze [k] [t])+""; }} while (! newpos.empty ()) {Position p1 = newpos.pop (); Ergebnis [p1.row-1] [p1.col-1] = "#"; } für (int k = 0; k <row; ++ k) {für (int t = 0; t <col; ++ T) {System.out.print (Resaugt [k] [t]+"/t"); } System.out.println (); }} int Maze [] []; private int row = 9; private int col = 8; Stapel <POSPOME> Stack; boolean p [] [] = null;} class Hallo {public static void main (String [] args) {Maze -Demo = new Maze (); Demo.init (); Demo.FindPath (); }} Auslaufbeispiel:
Bitte geben Sie die Anzahl der Zeilen des Labyrinths ein
3
Bitte geben Sie die Anzahl der Spalten in das Labyrinth ein
3
Bitte geben Sie ein Labyrinth von 3 Zeilen und 3 Spalten ein
0 1 1
0 0 1
1 0 0
Die Pfade sind wie folgt:
Bitte geben Sie die Anzahl der Zeilen des Labyrinths ein
9
Bitte geben Sie die Anzahl der Spalten in das Labyrinth ein
8
Bitte geben Sie ein Labyrinth von 9 Zeilen und 8 Spalten ein
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 1 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0 0 0 0
Die Pfade sind wie folgt:
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.