Use stack maze algorithm java version of the code
- 2021-01-02 21:51:41
- OfStack
This paper shares the use of stack maze algorithm java version, mainly to investigate 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 is available ) {
Mark that this location has been passed ;
Save the current location to merge into the stack ;
if( The current position is the endpoint ) {
End of the program ;
}
To obtain the 1 A position ;
}
else {
if( The stack is not empty ) {
Out of the stack;
while( The current position direction is 4 And the stack is not empty ) {
Mark the current location as not available ;
Out of the stack ;
}
if( The direction of the current position is less than 4) {
The direction of +1;
Back into the stack ;
To obtain the 1 A position ;
}
}
}
}
while ( The stack is not empty );
The java code is as follows:
import java.util.Stack;
public class Maze {
// The 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,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
{1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,1},
{1,1,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
{1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
{1,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1},
{1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
{1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1},
{1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
{1,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
};
// Marks whether the path has been passed
private int[][] mark = new int[MAZE_SIZE_X][MAZE_SIZE_Y];
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 is available
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));
// Has been to the finish line
if (curPos.x == END_X && curPos.y == END_Y) {
return;
}
curPos = nextPos(curPos, stack.peek().direction);
}
// To go
else {
if (!stack.isEmpty()) {
MazeNode curNode = stack.pop();
while (curNode.direction == 4 && !stack.isEmpty()) {
// If the current position 4 If all directions have been tried, mark the location as unreachable and push it out of the stack
mark[curNode.position.x][curNode.position.y] = 1;
curNode = stack.pop();
}
if (curNode.direction < 4) {
curNode.direction++;// The direction of +1
stack.push(curNode);// Back into the stack
curPos = nextPos(curNode.position, curNode.direction);// To obtain the 1 A position
}
}
}
}
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 locations of the points in the maze
class Position {
int x;
int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
// Nodes 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;
}
}
// Under the 1 I'm going to start at 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();
}
}