A M×N rectangular array represents the maze, and 0 and 1 represent the pathways and obstacles in the maze, respectively. Design a program to find a path from the entrance to the exit for any setting maze, or draw a conclusion that there is no path.
(1) Output the maze's graph according to the two-dimensional array.
(2) Explore the four directions of the maze: RIGHT is to the right, DOWN is to the down, LEFT is to the left, and UP is to the up, and output the walking path from the entrance to the exit.
example:
The upper left corner (1, 1) is the entrance, and the lower right corner (8, 9) is the exit.
You can use the backtracking method, that is, starting from the entrance and exploring in a certain direction. If it can be done, continue to move forward; otherwise, retreat along the original path, continue to explore in another direction until the exit position, and find a path. If all possible paths are explored and the exit is not reached, the labyrinth set has no paths.
import java.util.*;class 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<Position>(); p = new boolean[15][15]; } /* * Constructing maze*/ public void init(){ Scanner scanner = new Scanner(System.in); System.out.println("Please enter the number of rows of the maze"); row = scanner.nextInt(); System.out.println("Please enter the number of columns of the maze"); col = scanner.nextInt(); System.out.println("Please enter" + row + "row" + col + "column maze"); int temp = 0; for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp = scanner.nextInt(); maze[i][j] = temp; p[i][j] = false; } } } /* * Go back to the maze to see if there is a way out*/ public void findPath(){ // Give a circle of walls around the homes of the original maze 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[row + 1][j] = 1; temp[i][0] = temp[i][col + 1] = 1; } } // Copy the original maze into the new maze for(int i = 0; i < row; ++i) { for(int j = 0; j < col; ++j) { temp[i + 1][j + 1] = maze[i][j]; } } // Start querying clockwise from the upper left corner int i = 1; int j = 1; p[i][j] = true; stack.push(new 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(new Position(i, j + 1)); j++; } else if ((temp[i + 1][j] == 0) && (p[i + 1][j] == false)) { p[i + 1][j] = true; stack.push(new Position(i + 1, j)); i++; } else if ((temp[i][j - 1] == 0) && (p[i][j - 1] == false)) { p[i][j - 1] = true; stack.push(new Position(i, j - 1)); j--; } else if ((temp[i - 1][j] == 0) && (p[i - 1][j] == false)) { p[i - 1][j] = true; stack.push(new Position(i - 1, j)); i--; } 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("There is path"); System.out.println("The path is as follows:"); while (!stack.empty()) { Position pos = new Position(); pos = stack.pop(); newPos.push(pos); } } /* * Graphical output path* */ String result[][]=new String[row+1][col+1]; for(int k=0;k<row;++k){ for(int t=0;t<col;++t){ result[k][t]=(maze[k][t])+""; } } while (!newPos.empty()) { Position p1=newPos.pop(); result[p1.row-1][p1.col-1]="#"; } for(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 row = 9; private int col = 8; Stack<Position> stack; boolean p[][] = null;}class hello{ public static void main(String[] args){ Maze demo = new Maze(); demo.init(); demo.findPath(); }} Running example:
Please enter the number of rows of the maze
3
Please enter the number of columns in the maze
3
Please enter a maze of 3 rows and 3 columns
0 1 1
0 0 1
1 0 0
The paths are as follows:
Please enter the number of rows of the maze
9
Please enter the number of columns in the maze
8
Please enter a maze of 9 rows and 8 columns
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
The paths are as follows:
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.