This article shares the Java version of the maze algorithm using the stack, which mainly examines the use of the stack for your reference. The specific content is as follows
The main ideas are as follows:
do { if (the current position can be passed) { mark this position that has passed; save the current position and merge it into the stack; if (the current position is the end point) { program end; } Get the next position; } else { if (the stack is not empty) { out of stack; while (the current position direction is 4 and the stack is not empty) { mark the current position that cannot be moved; out of stack; } if (the direction of the current position is less than 4) { direction +1; re-enter the stack; get the next position; } } }} while (the stack is not empty);The java code is as follows:
import java.util.Stack;public class Maze { // stack private Stack<MazeNode> stack = new Stack<Maze.MazeNode>(); // maze private int[][] maze = { {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,0,1,0,0,0,1,1,1,1,1,1,1}, {1,0,1,1,0,0,0,0,1,1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 {1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1}, {1,1,0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, private static final int MAZE_SIZE_X = 14; private static final int MAZE_SIZE_Y = 17; private static final int END_X = 12; private static final int END_Y = 15; private void initMark() { for (int i = 0; i < MAZE_SIZE_X; i++) { for (int j = 0; j < MAZE_SIZE_Y; j++) { mark[i][j] = 0; } } } public void process() { initMark(); Position curPos = new Position(1, 1); do { // This path can be used if (maze[curPos.x][curPos.y] == 0 && mark[curPos.x][curPos.y] == 0) { mark[curPos.x][curPos.y] = 1; stack.push(new MazeNode(curPos, 1)); // End point if (curPos.x == END_X && curPos.y == END_Y) { return; } curPos = nextPos(curPos, stack.peek().direction); } // Not able to go else { if (!stack.isEmpty()) { MazeNode curNode = stack.pop(); while (curNode.direction == 4 && !stack.isEmpty()) { // If all 4 directions of the current position have been tried, then mark the position that cannot be moved and mark[curNode.position.x][curNode.position.y] = 1; curNode = stack.pop(); } if (curNode.direction < 4) { curNode.direction++;// Direction +1 stack.push(curNode);// Re-enter curPos = nextPos(curNode.position, curNode.direction);// Get the next location} } } } while(!stack.isEmpty()); } public void drawMaze() { for (int i = 0; i < maze.length; i++) { for (int j = 0; j < maze[0].length; j++) { System.out.print(maze[i][j]); } System.out.print("/n"); } System.out.print("/n"); } public void drawResult() { initMark(); MazeNode node; while (!stack.isEmpty()) { node = stack.pop(); mark[node.position.x][node.position.y] = 1; } for (int i = 0; i < mark.length; i++) { for (int j = 0; j < mark[0].length; j++) { System.out.print(mark[i][j]); } System.out.print("/n"); } System.out.print("/n"); } // Record the position of points in the maze class Position { int x; int y; public Position(int x, int y) { this.x = x; this.y = y; } } // Node in the stack class MazeNode { Position position; int direction; public MazeNode(Position pos) { this.position = pos; } public MazeNode(Position pos, int dir) { this.position = pos; this.direction = dir; } } // Next position, starting from the right, clockwise public Position nextPos(Position position, int direction) { Position newPosition = new Position(position.x, position.y); switch (direction) { case 1: newPosition.y += 1; break; case 2: newPosition.x += 1; break; case 3: newPosition.y -= 1; break; case 4: newPosition.x -= 1; break; default: break; } return newPosition; } public static void main(String[] args) { Maze maze = new Maze(); maze.drawMaze(); maze.process(); maze.drawResult(); }}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.