使用栈的迷宫算法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();  }}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持武林网。