查看: 3186|回复: 0

[Java语言] 使用栈的迷宫算法java版代码

发表于 2018-2-24 08:00:02

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

主要思路如下:

  1. do {
  2. if(当前位置可通过) {
  3. 标记此位置已走过;
  4. 保存当前位置并入栈;
  5. if(当前位置为终点) {
  6. 程序结束;
  7. }
  8. 获取下一个位置;
  9. }
  10. else {
  11. if(栈非空) {
  12. 出栈;
  13. while(当前位置方向为4且栈非空) {
  14. 标记当前位置不可走;
  15. 出栈;
  16. }
  17. if(当前位置的方向小于4) {
  18. 方向+1;
  19. 重新入栈;
  20. 获取下一个位置;
  21. }
  22. }
  23. }
  24. }
  25. while (栈非空);
复制代码

java代码如下:

  1. import java.util.Stack;
  2. public class Maze {
  3. // 栈
  4. private Stack<MazeNode> stack = new Stack<Maze.MazeNode>();
  5. // 迷宫
  6. private int[][] maze = {
  7. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
  8. {1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},
  9. {1,0,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},
  10. {1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},
  11. {1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,1},
  12. {1,1,0,0,1,0,0,1,0,1,1,1,1,1,1,1,1},
  13. {1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
  14. {1,0,0,1,1,1,1,1,1,0,1,0,0,1,0,1,1},
  15. {1,0,1,1,1,0,0,0,0,1,1,1,1,1,1,1,1},
  16. {1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},
  17. {1,1,0,0,0,0,1,1,0,1,0,0,0,0,0,0,1},
  18. {1,1,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},
  19. {1,0,0,0,0,1,1,1,1,1,0,1,1,1,1,0,1},
  20. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
  21. };
  22. // 标记路径是否已走过
  23. private int[][] mark = new int[MAZE_SIZE_X][MAZE_SIZE_Y];
  24. private static final int MAZE_SIZE_X = 14;
  25. private static final int MAZE_SIZE_Y = 17;
  26. private static final int END_X = 12;
  27. private static final int END_Y = 15;
  28. private void initMark() {
  29. for (int i = 0; i < MAZE_SIZE_X; i++) {
  30. for (int j = 0; j < MAZE_SIZE_Y; j++) {
  31. mark[i][j] = 0;
  32. }
  33. }
  34. }
  35. public void process() {
  36. initMark();
  37. Position curPos = new Position(1, 1);
  38. do {
  39. // 此路径可走
  40. if (maze[curPos.x][curPos.y] == 0 && mark[curPos.x][curPos.y] == 0) {
  41. mark[curPos.x][curPos.y] = 1;
  42. stack.push(new MazeNode(curPos, 1));
  43. // 已到终点
  44. if (curPos.x == END_X && curPos.y == END_Y) {
  45. return;
  46. }
  47. curPos = nextPos(curPos, stack.peek().direction);
  48. }
  49. // 走不通
  50. else {
  51. if (!stack.isEmpty()) {
  52. MazeNode curNode = stack.pop();
  53. while (curNode.direction == 4 && !stack.isEmpty()) {
  54. // 如果当前位置的4个方向都已试过,那么标记该位置不可走,并出栈
  55. mark[curNode.position.x][curNode.position.y] = 1;
  56. curNode = stack.pop();
  57. }
  58. if (curNode.direction < 4) {
  59. curNode.direction++;// 方向+1
  60. stack.push(curNode);// 重新入栈
  61. curPos = nextPos(curNode.position, curNode.direction);// 获取下一个位置
  62. }
  63. }
  64. }
  65. }
  66. while(!stack.isEmpty());
  67. }
  68. public void drawMaze() {
  69. for (int i = 0; i < maze.length; i++) {
  70. for (int j = 0; j < maze[0].length; j++) {
  71. System.out.print(maze[i][j]);
  72. }
  73. System.out.print("\n");
  74. }
  75. System.out.print("\n");
  76. }
  77. public void drawResult() {
  78. initMark();
  79. MazeNode node;
  80. while (!stack.isEmpty()) {
  81. node = stack.pop();
  82. mark[node.position.x][node.position.y] = 1;
  83. }
  84. for (int i = 0; i < mark.length; i++) {
  85. for (int j = 0; j < mark[0].length; j++) {
  86. System.out.print(mark[i][j]);
  87. }
  88. System.out.print("\n");
  89. }
  90. System.out.print("\n");
  91. }
  92. // 记录迷宫中的点的位置
  93. class Position {
  94. int x;
  95. int y;
  96. public Position(int x, int y) {
  97. this.x = x;
  98. this.y = y;
  99. }
  100. }
  101. // 栈中的结点
  102. class MazeNode {
  103. Position position;
  104. int direction;
  105. public MazeNode(Position pos) {
  106. this.position = pos;
  107. }
  108. public MazeNode(Position pos, int dir) {
  109. this.position = pos;
  110. this.direction = dir;
  111. }
  112. }
  113. // 下一个位置,从右开始,顺时针
  114. public Position nextPos(Position position, int direction) {
  115. Position newPosition = new Position(position.x, position.y);
  116. switch (direction) {
  117. case 1:
  118. newPosition.y += 1;
  119. break;
  120. case 2:
  121. newPosition.x += 1;
  122. break;
  123. case 3:
  124. newPosition.y -= 1;
  125. break;
  126. case 4:
  127. newPosition.x -= 1;
  128. break;
  129. default:
  130. break;
  131. }
  132. return newPosition;
  133. }
  134. public static void main(String[] args) {
  135. Maze maze = new Maze();
  136. maze.drawMaze();
  137. maze.process();
  138. maze.drawResult();
  139. }
  140. }
复制代码

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持程序员之家。



回复

使用道具 举报