Un réseau rectangulaire M × N représente le labyrinthe, et 0 et 1 représentent respectivement les voies et les obstacles dans le labyrinthe. Concevez un programme pour trouver un chemin à partir de l'entrée de la sortie pour tout labyrinthe de réglage, ou tirez une conclusion qu'il n'y a pas de chemin.
(1) Sortir le graphique du labyrinthe en fonction du tableau bidimensionnel.
(2) Explorer les quatre directions du labyrinthe: à droite est à droite, vers le bas est vers le bas, la gauche est à gauche, et vers le haut, et la sortie du chemin de marche de l'entrée de la sortie.
exemple:
Le coin supérieur gauche (1, 1) est l'entrée, et le coin inférieur droit (8, 9) est la sortie.
Vous pouvez utiliser la méthode de retour en arrière, c'est-à-dire à partir de l'entrée et à l'exploration dans une certaine direction. Si cela peut être fait, continuez à avancer; Sinon, reculez le long du chemin d'origine, continuez d'explorer dans une autre direction jusqu'à la position de sortie et trouvez un chemin. Si tous les chemins possibles sont explorés et que la sortie n'est pas atteinte, l'ensemble du labyrinthe n'a pas de chemins.
import java.util. *; position de classe {position publique () {} position publique (int row, int col) {this.col = col; this.row = row; } public String toString () {return "(" + row + "," + col + ")"; } int row; int col;} class kaze {public kaze () {kaze = new int [15] [15]; stack = new Stack <Position> (); p = nouveau booléen [15] [15]; } / * * Construire le labyrinthe * / public void init () {Scanner Scanner = new Scanner (System.in); System.out.println ("Veuillez saisir le nombre de lignes du labyrinthe"); row = scanner.nextint (); System.out.println ("Veuillez saisir le nombre de colonnes du labyrinthe"); Col = Scanner.Nextint (); System.out.println ("s'il vous plaît entre" + row + "row" + col + "colonne Maze"); int temp = 0; for (int i = 0; i <row; ++ i) {for (int j = 0; j <col; ++ j) {temp = scanner.nextint (); labyrinthe [i] [j] = temp; p [i] [j] = false; }}} / * * Retournez dans le labyrinthe pour voir s'il y a une issue * / public void findPath () {// Donnez un cercle de murs autour des maisons du labyrinthe d'origine int temp [] [] = new int [Row + 2] [col + 2]; for (int i = 0; i <row + 2; ++ i) {for (int j = 0; j <col + 2; ++ j) {temp [0] [j] = 1; temp [ligne + 1] [j] = 1; temp [i] [0] = temp [i] [col + 1] = 1; }} // Copiez le labyrinthe d'origine dans le nouveau labyrinthe pour (int i = 0; i <row; ++ i) {for (int j = 0; j <col; ++ j) {temp [i + 1] [j + 1] = labyrinthe [i] [j]; }} // Démarrer l'interrogation dans le sens des aiguilles d'une montre à partir du coin supérieur gauche int i = 1; int j = 1; p [i] [j] = true; stack.push (nouvelle 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 (nouvelle position (i, j + 1)); j ++; } else if ((temp [i + 1] [j] == 0) && (p [i + 1] [j] == false)) {p [i + 1] [j] = true; stack.push (nouvelle position (i + 1, j)); i ++; } else if ((temp [i] [j - 1] == 0) && (p [i] [j - 1] == false)) {p [i] [j - 1] = true; stack.push (nouvelle position (i, j - 1)); J-; } else if ((temp [i - 1] [j] == 0) && (p [i - 1] [j] == false)) {p [i - 1] [j] = true; stack.push (nouvelle position (i - 1, j)); je--; } else {stack.pop (); if (stack.empty ()) {break; } i = stack.Peek (). Row; j = stack.Peek (). Col; }} Pile <Position> newPos = new Stack <post> (); if (stack.empty ()) {break; } i = stack.Peek (). Row; j = stack.Peek (). Col; }} Pile <Position> newPos = new Stack <post> (); if (stack.empty ()) {System.out.println ("No Path"); } else {System.out.println ("il y a path"); System.out.println ("Le chemin est le suivant:"); while (! stack.empty ()) {position pos = new position (); pos = stack.pop (); Newpos.push (pos); }} / * * Path de sortie graphique * * / String result [] [] = new String [Row + 1] [Col + 1]; pour (int k = 0; k <row; ++ k) {for (int t = 0; t <col; ++ t) {result [k] [t] = (labyrinthe [k] [t]) + ""; }} while (! newpos.empty ()) {position p1 = newpos.pop (); résultat [p1.row-1] [p1.col-1] = "#"; } pour (int k = 0; k <row; ++ k) {for (int t = 0; t <col; ++ t) {System.out.print (resault [k] [t] + "/ t"); } System.out.println (); }} int Maze [] []; Int privé Int Row = 9; private int col = 8; Pile <Position> pile; booléen p [] [] = null;} classe bonjour {public static void main (String [] args) {Maze Demo = new Maze (); Demo.init (); Demo.FindPath (); }} Exemple en cours d'exécution:
Veuillez saisir le nombre de lignes du labyrinthe
3
Veuillez saisir le nombre de colonnes dans le labyrinthe
3
Veuillez entrer un dédale de 3 rangées et 3 colonnes
0 1 1
0 0 1
1 0 0
Les chemins sont les suivants:
Veuillez saisir le nombre de lignes du labyrinthe
9
Veuillez saisir le nombre de colonnes dans le labyrinthe
8
Veuillez entrer dans un labyrinthe de 9 rangées et 8 colonnes
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 0 0 0 1 0 1
1 1 0 0 0 0 0 0 0 0
Les chemins sont les suivants:
Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.