使用栈的迷宫算法java版代码

本文为大家分享了使用栈的迷宫算法java版，主要考察栈的使用，供大家参考，具体内容如下

主要思路如下：

do {
if(当前位置可通过) {
 标记此位置已走过;
 保存当前位置并入栈;
 if(当前位置为终点) {
  程序结束;
 }
 获取下一个位置;
}
else {
 if(栈非空) {
  出栈；
  while(当前位置方向为4且栈非空) {
   标记当前位置不可走;
   出栈;
  }
  if(当前位置的方向小于4) {
   方向+1;
   重新入栈;
   获取下一个位置;
  }
 }
}
}
while (栈非空);

java代码如下：

import java.util.Stack;

public class Maze {

// 栈
private Stack<MazeNode> stack = new Stack<Maze.MazeNode>();
// 迷宫
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},
};
// 标记路径是否已走过
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 {
  // 此路径可走
  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));
   // 已到终点
   if (curPos.x == END_X && curPos.y == END_Y) {
    return;
   }
   curPos = nextPos(curPos, stack.peek().direction);
  }
  // 走不通
  else {
   if (!stack.isEmpty()) {
    MazeNode curNode = stack.pop();
    while (curNode.direction == 4 && !stack.isEmpty()) {
     // 如果当前位置的4个方向都已试过，那么标记该位置不可走，并出栈
     mark[curNode.position.x][curNode.position.y] = 1;
     curNode = stack.pop();
    }
    if (curNode.direction < 4) {
     curNode.direction++;// 方向+1
     stack.push(curNode);// 重新入栈
     curPos = nextPos(curNode.position, curNode.direction);// 获取下一个位置
    }
   }
  }
 }
 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");
}

// 记录迷宫中的点的位置
class Position {
 int x;
 int y;

public Position(int x, int y) {
  this.x = x;
  this.y = y;
 }
}

// 栈中的结点
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;
 }
}

// 下一个位置，从右开始，顺时针
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();
}

}

来源：http://blog.csdn.net/Young_Leez/article/details/44026295