Una matriz rectangular M × N representa el laberinto, y 0 y 1 representan las vías y obstáculos en el laberinto, respectivamente. Diseñe un programa para encontrar una ruta desde la entrada a la salida para cualquier laberinto de configuración, o sacar una conclusión de que no hay camino.
(1) Extienda el gráfico del laberinto de acuerdo con la matriz bidimensional.
(2) Explore las cuatro instrucciones del laberinto: a la derecha es a la derecha, hacia abajo es hacia abajo, a la izquierda está a la izquierda y arriba es hacia arriba y emite la ruta de caminata desde la entrada a la salida.
ejemplo:
La esquina superior izquierda (1, 1) es la entrada, y la esquina inferior derecha (8, 9) es la salida.
Puede usar el método de retroceso, es decir, comenzando desde la entrada y explorando en cierta dirección. Si se puede hacer, continúe avanzando; De lo contrario, retire a lo largo del camino original, continúe explorando en otra dirección hasta la posición de salida y encuentre un camino. Si se exploran todas las rutas posibles y no se alcanza la salida, el conjunto de laberinto no tiene caminos.
import java.util.*; class Position {public Position () {} Public Position (int fila, int col) {this.col = col; this.row = fila; } public String toString () {return "(" + row + "," + col + ")"; } int fila; int col;} class Maze {public Maze () {Maze = new int [15] [15]; stack = new Stack <Sotion> (); p = nuevo booleano [15] [15]; } /** Construyendo laberinto* / public void init () {Scanner Scanner = New Scanner (System.in); System.out.println ("Ingrese el número de filas del laberinto"); fila = scanner.nextInt (); System.out.println ("Ingrese el número de columnas del laberinto"); col = Scanner.NextInt (); System.out.println ("por favor ingrese" + fila + "fila" + col + "laberinto de columna"); int temp = 0; for (int i = 0; i <row; ++ i) {for (int j = 0; j <col; ++ j) {temp = scanner.nextInt (); laberinto [i] [j] = temp; p [i] [j] = falso; }}} /** Regrese al laberinto para ver si hay una salida* / public void findPath () {// Dé un círculo de paredes alrededor de las casas del Maze intemperánego original [] [] = nuevo int [fila + 2] [col + 2]; for (int i = 0; i <row +2; ++ i) {for (int j = 0; j <col +2; ++ j) {temp [0] [j] = 1; tempt [fila + 1] [j] = 1; temp [i] [0] = temp [i] [col + 1] = 1; }} // Copiar el laberinto original en el nuevo laberinto para (int i = 0; i <row; ++ i) {para (int j = 0; j <col; ++ j) {temp [i +1] [j +1] = labere [i] [j]; }} // Comience a consultar en el sentido de las agujas del reloj desde la esquina superior izquierda int i = 1; int j = 1; p [i] [j] = true; stack.push (nueva posición (i, j)); while (! stack.empty () && (! (i == (row) && (j == col))))) {if ((temp [i] [j + 1] == 0) && (p [i] [j + 1] == falso)) {P [i] [j + 1] = true; stack.push (nueva posición (i, j + 1)); j ++; } else if ((temp [i + 1] [j] == 0) && (p [i + 1] [j] == falso)) {p [i + 1] [j] = true; stack.push (nueva posición (i + 1, j)); i ++; } else if ((temp [i] [j - 1] == 0) && (p [i] [j - 1] == falso)) {p [i] [j - 1] = true; stack.push (nueva posición (i, j - 1)); J--; } else if ((temp [i - 1] [j] == 0) && (p [i - 1] [j] == falso)) {p [i - 1] [j] = true; stack.push (nueva posición (i - 1, j)); i--; } else {stack.pop (); if (stack.empty ()) {break; } i = stack.peek (). fila; j = stack.peek (). col; }} Pila <posicion> newpos = new Stack <Sosion> (); if (stack.empty ()) {break; } i = stack.peek (). fila; j = stack.peek (). col; }} Pila <posicion> newpos = new Stack <Sosion> (); if (stack.empty ()) {system.out.println ("sin ruta"); } else {System.out.println ("Hay ruta"); System.out.println ("La ruta es la siguiente:"); while (! stack.empty ()) {posición pos = nueva posición (); pos = stack.pop (); newpos.push (pos); }} / * * Ruta de salida gráfica * * / string result [] [] = nueva cadena [fila+1] [col+1]; para (int k = 0; k <row; ++ k) {for (int t = 0; t <col; ++ t) {resultado [k] [t] = (laberinto [k] [t])+""; }} while (! Newpos.empty ()) {posición p1 = newpos.pop (); resultado [p1.row-1] [p1.col-1] = "#"; } para (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 [] []; private int fila = 9; privado int col = 8; Pila <sition> pila; boolean p [] [] = null;} class Hello {public static void main (string [] args) {Maze demo = new Maze (); demo.init (); demo.findpath (); }} Ejemplo de ejecución:
Ingrese el número de filas del laberinto
3
Ingrese el número de columnas en el laberinto
3
Ingrese un laberinto de 3 filas y 3 columnas
0 1 1
0 0 1
1 0 0
Los caminos son los siguientes:
Ingrese el número de filas del laberinto
9
Ingrese el número de columnas en el laberinto
8
Ingrese un laberinto de 9 filas y 8 columnas
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
Los caminos son los siguientes:
Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.