Uma matriz retangular m × n representa o labirinto e 0 e 1 representam as vias e obstáculos no labirinto, respectivamente. Projete um programa para encontrar um caminho da entrada para a saída para qualquer labirinto de configuração ou tirar uma conclusão de que não há caminho.
(1) Saia do gráfico do labirinto de acordo com a matriz bidimensional.
(2) Explore as quatro direções do labirinto: a direita está para a direita, para baixo, está para baixo, a esquerda está para a esquerda e para cima é para cima, e a saída do caminho de caminhada da entrada para a saída.
exemplo:
O canto superior esquerdo (1, 1) é a entrada e o canto inferior direito (8, 9) é a saída.
Você pode usar o método de backtracking, ou seja, a partir da entrada e explorando em uma certa direção. Se puder ser feito, continue avançando; Caso contrário, recue ao longo do caminho original, continue a explorar em outra direção até a posição de saída e encontrar um caminho. Se todos os caminhos possíveis forem explorados e a saída não for alcançada, o conjunto de labirintos não terá caminhos.
importar java.Util. this.row = linha; } public string tostring () {return "(" + linha + "," + col + ")"; } int linha; int col;} classe Maze {public Maze () {Maze = new int [15] [15]; pilha = new Stack <Pusition> (); p = novo booleano [15] [15]; } /** Construindo labirinto* / public void init () {scanner scanner = new Scanner (System.in); System.out.println ("Por favor, insira o número de linhas do labirinto"); linha = scanner.NextInt (); System.out.println ("Por favor, insira o número de colunas do labirinto"); col = scanner.NextInt (); System.out.println ("Por favor, digite" + linha + "linha" + col + "coluna Maze"); int temp = 0; for (int i = 0; i <linha; ++ i) {for (int j = 0; j <col; ++ j) {temp = scanner.nextint (); labirinto [i] [j] = temp; p [i] [j] = false; }}} /** Volte ao labirinto para ver se existe uma saída* / public void findPath () {// Dê um círculo de paredes ao redor das casas do labirinto original int temp [] [] = new int [linha + 2] [col + 2]; for (int i = 0; i <linha +2; ++ i) {for (int j = 0; j <col +2; ++ j) {temp [0] [j] = 1; temp [linha + 1] [j] = 1; temp [i] [0] = temp [i] [col + 1] = 1; }} // copie o labirinto original no novo labirinto para (int i = 0; i <linha; ++ i) {for (int j = 0; j <col; ++ j) {temp [i +1] [j +1] = labirinto [i] [j]; }} // Comece a consultar no sentido horário no canto superior esquerdo int i = 1; int j = 1; p [i] [j] = true; Stack.push (nova posição (i, j)); while (! stack.empty () && (! (i == (linha) && (j == col)))) {if ((temp [i] [j + 1] == 0) && (p [i] [j + 1] == false)) {p [i] [j + 1] = true; Stack.push (nova posição (i, j + 1)); j ++; } else if ((temp [i + 1] [j] == 0) && (p [i + 1] [j] == false)) {p [i + 1] [j] = true; Stack.push (nova posição (i + 1, j)); i ++; } else if ((temp [i] [j - 1] == 0) && (p [i] [j - 1] == false)) {p [i] [j - 1] = true; Stack.push (nova posição (i, j - 1)); J--; } else if ((temp [i - 1] [j] == 0) && (p [i - 1] [j] == false)) {p [i - 1] [j] = true; Stack.push (nova posição (i - 1, j)); eu--; } else {Stack.pop (); if (Stack.Empty ()) {break; } i = Stack.peek (). Row; j = Stack.peek (). Col; }} Pilha <Position> newpos = new Stack <Pusition> (); if (Stack.Empty ()) {break; } i = Stack.peek (). Row; j = Stack.peek (). Col; }} Pilha <Position> newpos = new Stack <Pusition> (); if (Stack.Empty ()) {System.out.println ("No Path"); } else {System.out.println ("há caminho"); System.out.println ("O caminho é o seguinte:"); while (! Stack.Empty ()) {Position pos = new Pusicion (); POS = Stack.pop (); newpos.push (POS); }} / * * Caminho de saída gráfico * * / string resultado [] [] = new String [linha+1] [col+1]; for (int k = 0; k <row; ++ k) {for (int t = 0; t <col; ++ t) {resultado [k] [t] = (labirinto [k] [t])+""; }} while (! newpos.empty ()) {Posição 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 (Rousult [k] [t]+"/t"); } System.out.println (); }} int MAZE [] []; private int linha = 9; privado int col = 8; Pilha <osition> pilha; boolean p [] [] = null;} classe hello {public static void main (string [] args) {Maze Demo = new Maze (); Demo.init (); Demo.findPath (); }} Exemplo de execução:
Por favor, insira o número de linhas do labirinto
3
Por favor, insira o número de colunas no labirinto
3
Por favor, insira um labirinto de 3 linhas e 3 colunas
0 1 1
0 0 1
1 0 0
Os caminhos são os seguintes:
Por favor, insira o número de linhas do labirinto
9
Por favor, insira o número de colunas no labirinto
8
Por favor, insira um labirinto de 9 linhas e 8 colunas
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 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
Os caminhos são os seguintes:
O exposto acima é todo o conteúdo deste artigo. Espero que seja útil para o aprendizado de todos e espero que todos apoiem mais o wulin.com.