如何在java中找到迷宫的其他解决方案?

kzmpq1sx  于 2021-07-06  发布在  Java
关注(0)|答案(1)|浏览(335)

我需要写一个程序,在给定的txt文件迷宫和打印解决方案的路径控制台。我写了这个程序,你可以看到下面,但我只能找到一个解决方案。如果迷宫里有不止一个解,我需要找到所有这些。我不知道我应该采取什么方法来解决这个问题。你能给个主意吗?
这是我的作品:
maze.txt(作为参数发送)

  1. 11111111111111111
  2. 10110011000111111
  3. 11001110111001111
  4. 10110001011100111
  5. 11101111011011001
  6. 11101001011011111
  7. 11011011011001011
  8. 10111100111110111
  9. 11011011011111101
  10. 11100111011000011
  11. 10011110100111101
  12. 10100110111111101
  13. 11111111111111111

驾驶员等级:

  1. import java.io.*;
  2. import java.util.Arrays;
  3. public class Driver {
  4. public static void main(String[] args) {
  5. //Reading source file
  6. int rowNum = 0, colNum = 0;
  7. File mazeFile = new File(args[0]);
  8. try (BufferedReader br = new BufferedReader(new FileReader(mazeFile))) {
  9. System.out.println("Input of Readed File:\n");
  10. String line;
  11. while ((line = br.readLine()) != null) {
  12. colNum = line.length();
  13. rowNum++;
  14. System.out.println(line);
  15. }
  16. } catch (IOException e) {
  17. e.printStackTrace();
  18. }
  19. //creating new maze array
  20. char[][] maze = new char[rowNum][colNum];
  21. System.out.println();
  22. System.out.print("ROW: "+rowNum+" COL: "+colNum);
  23. //Setting maze's elements
  24. try (BufferedReader br = new BufferedReader(new FileReader(mazeFile))) {
  25. int readed,rNum=0,cNum=0;
  26. while ((readed = br.read()) != -1) {
  27. if(readed == 10){
  28. }
  29. else if(rNum<rowNum && cNum < colNum){
  30. maze[rNum][cNum] = (char)readed;
  31. cNum++;
  32. }
  33. else if(cNum >= colNum){
  34. rNum++;
  35. cNum=0;
  36. }
  37. }
  38. } catch (IOException e) {
  39. e.printStackTrace();
  40. }
  41. //Printing created maze...
  42. System.out.println("\nCreated Maze: \n");
  43. for (int i = 0; i<rowNum ; i++) {
  44. for (int j = 0; j < colNum; j++) {
  45. System.out.print(maze[i][j]);
  46. }
  47. System.out.println();
  48. }
  49. System.out.println("\nSolution: \n");
  50. //Creating myStack object for making stack operations
  51. Stack myStack = new Stack(1000);
  52. //Creating mazeSolver object for solving maze
  53. MazeSolver mazeSolver = new MazeSolver(myStack,maze,1,1,colNum-2,rowNum-2,rowNum,colNum);
  54. mazeSolver.solve();
  55. //Printing inside of our stack.
  56. //myStack.showElements();
  57. //Creating answer array
  58. char[][] answer = maze;
  59. //Our path is drawn by re-reading the stored data in our stack structure.
  60. for (int i = rowNum-1; i >=0; i--) {
  61. for (int j = colNum-1; j >=0; j--) {
  62. int x[] = myStack.peek();
  63. if(i == x[0] && j == x[1]){
  64. answer[i][j] = '#';
  65. }
  66. }
  67. }
  68. //Minor visual improvements ...
  69. for (int i = 0; i<rowNum ; i++) {
  70. for (int j = 0; j < colNum; j++) {
  71. if(answer[i][j] == '1' || answer[i][j] == '0')
  72. answer[i][j] = '.';
  73. }
  74. }
  75. //Printing our answer
  76. for (int i = 0; i<rowNum ; i++) {
  77. for (int j = 0; j < colNum; j++) {
  78. System.out.print(maze[i][j]);
  79. }
  80. System.out.println();
  81. }
  82. }
  83. }

堆栈类:

  1. public class Stack {
  2. int topOfStack;
  3. int capacity;
  4. int[][] Stack;
  5. public Stack(int capacity) {
  6. this.capacity = capacity;
  7. Stack = new int[capacity][2];
  8. topOfStack = -1;
  9. }
  10. void push(int y, int x)
  11. {
  12. if(topOfStack == capacity){
  13. System.out.println("Stack Overflow...");
  14. }
  15. else{
  16. Stack[++topOfStack] = new int[] { y, x };
  17. }
  18. //System.out.println("###Pushed Element: "+Stack[topOfStack][0]+" "+Stack[topOfStack][1]);
  19. }
  20. int[] pop() {
  21. if (topOfStack < 0) {
  22. System.out.println("Stack is empty...");
  23. return null;
  24. }
  25. //System.out.println("Pulled Element: "+Stack[topOfStack][0]+" "+Stack[topOfStack][1]);
  26. topOfStack--;
  27. return Stack[topOfStack];
  28. }
  29. int[] pop2() {
  30. if (topOfStack < 0) {
  31. System.out.println("Stack Underflow");
  32. return null;
  33. }
  34. else {
  35. int x[] = Stack[topOfStack--];
  36. //System.out.println("Pulled Element: "+x[0]+" "+x[1]);
  37. return x;
  38. }
  39. }
  40. int[] peek()
  41. {
  42. if (topOfStack < 0) {
  43. System.out.println("Stack Underflow");
  44. return null;
  45. }
  46. else {
  47. int x[] = Stack[topOfStack];
  48. return x;
  49. }
  50. }
  51. void showElements()
  52. {
  53. System.out.println("\n\n");
  54. for (int i = topOfStack; i >=0; i--) {
  55. System.out.println("Stack Elements "+i+":"+" "+Stack[i][0] +" "+Stack[i][1]);
  56. }
  57. }
  58. int size(){
  59. int i;
  60. for (i = 0; i <= topOfStack; i++) {
  61. }
  62. return i;
  63. }
  64. }

mazesolver等级:

  1. public class MazeSolver {
  2. Stack workStack;
  3. char[][] maze;
  4. int startPointX;
  5. int startPointY;
  6. int endPointX;
  7. int endPointY;
  8. int numberOfRows;
  9. int numberOfCols;
  10. static final char Wall = '1';
  11. static final char Free = '0';
  12. static final char Success = '#';
  13. public MazeSolver(Stack workStack, char[][] maze,int startingPointX, int startingPointY, int endPointX, int endPointY, int RowNum, int ColNum) {
  14. this.workStack = workStack;
  15. this.maze = maze;
  16. this.startPointX = startingPointX;
  17. this.startPointY = startingPointY;
  18. this.endPointX = endPointX;
  19. this.endPointY = endPointY;
  20. this.numberOfRows = RowNum;
  21. this.numberOfCols = ColNum;
  22. workStack.push(startPointY,startingPointX);
  23. }
  24. boolean canMoveEast(){
  25. if((maze[startPointY][startPointX + 1] == Free) && (startPointX + 1 <= numberOfCols))
  26. {
  27. return true;
  28. }
  29. else
  30. return false;
  31. }
  32. boolean canMoveWest(){
  33. if((maze[startPointY][startPointX - 1] == Free) && (startPointX - 1 <= numberOfCols)){
  34. return true;
  35. }
  36. else
  37. return false;
  38. }
  39. boolean canMoveNorth(){
  40. if((maze[startPointY-1][startPointX] == Free) && (startPointY - 1 <= numberOfRows)){
  41. return true;
  42. }
  43. else
  44. return false;
  45. }
  46. boolean canMoveSouth(){
  47. if((maze[startPointY+1][startPointX] == Free) && (startPointY + 1 <= numberOfRows)){
  48. return true;
  49. }
  50. else
  51. return false;
  52. }
  53. boolean canMoveNorthEast(){
  54. if((maze[startPointY-1][startPointX+1] == Free) && (startPointY - 1 <= numberOfRows) && (startPointX + 1 <= numberOfCols)){
  55. return true;
  56. }
  57. else
  58. return false;
  59. }
  60. boolean canMoveNorthWest(){
  61. if((maze[startPointY-1][startPointX-1] == Free) && (startPointY - 1 <= numberOfRows) && (startPointX - 1 <= numberOfCols)){
  62. return true;
  63. }
  64. else
  65. return false;
  66. }
  67. boolean canMoveSouthEast(){
  68. if((maze[startPointY+1][startPointX+1] == Free) && (startPointY + 1 <= numberOfRows) && (startPointX + 1 <= numberOfCols)){
  69. return true;
  70. }
  71. else
  72. return false;
  73. }
  74. boolean canMoveSouthWest(){
  75. if((maze[startPointY+1][startPointX-1] == Free) && (startPointY + 1 <= numberOfRows) && (startPointX - 1 <= numberOfCols)){
  76. return true;
  77. }
  78. else
  79. return false;
  80. }
  81. boolean solve()
  82. {
  83. maze[startPointY][startPointX] = Success;
  84. //Checked if we reached our goal
  85. if((startPointY == endPointY) && (startPointX == endPointX)){
  86. return true;
  87. }
  88. if(canMoveEast()){
  89. workStack.push(startPointY,startPointX+1);
  90. startPointX++;
  91. solve();
  92. }
  93. else if(canMoveWest()){
  94. workStack.push(startPointY,startPointX-1);
  95. startPointX--;
  96. solve();
  97. }
  98. else if(canMoveNorth()){
  99. workStack.push(startPointY-1,startPointX);
  100. startPointY--;
  101. solve();
  102. }
  103. else if(canMoveSouth()){
  104. workStack.push(startPointY+1,startPointX);
  105. startPointY++;
  106. solve();
  107. }
  108. else if(canMoveNorthEast()){
  109. workStack.push(startPointY-1,startPointX+1);
  110. startPointY--;
  111. startPointX++;
  112. solve();
  113. }
  114. else if(canMoveNorthWest()){
  115. workStack.push(startPointY-1,startPointX-1);
  116. startPointY--;
  117. startPointX--;
  118. solve();
  119. }
  120. else if(canMoveSouthEast()){
  121. workStack.push(startPointY+1,startPointX+1);
  122. startPointY++;
  123. startPointX++;
  124. solve();
  125. }
  126. else if(canMoveSouthWest()){
  127. workStack.push(startPointY+1,startPointX-1);
  128. startPointY++;
  129. startPointX--;
  130. solve();
  131. }
  132. else if(true){
  133. try {
  134. maze[startPointY][startPointX] = Wall;
  135. int[] back = workStack.pop();
  136. startPointY = back[0];
  137. startPointX = back[1];
  138. solve();
  139. } catch (Exception e) {
  140. System.out.println("There is no solution!");
  141. System.exit(0);
  142. }
  143. }
  144. return false;
  145. }
  146. }

我得到的输出:

  1. Input of Readed File:
  2. 11111111111111111
  3. 10110011000111111
  4. 11001110111001111
  5. 10110001011100111
  6. 11101111011011001
  7. 11101001011011111
  8. 11011011011001011
  9. 10111100111110111
  10. 11011011011111101
  11. 11100111011000011
  12. 10011110100111101
  13. 10100110111111101
  14. 11111111111111111
  15. ROW: 13 COL: 17
  16. Created Maze:
  17. 11111111111111111
  18. 10110011000111111
  19. 11001110111001111
  20. 10110001011100111
  21. 11101111011011001
  22. 11101001011011111
  23. 11011011011001011
  24. 10111100111110111
  25. 11011011011111101
  26. 11100111011000011
  27. 10011110100111101
  28. 10100110111111101
  29. 11111111111111111
  30. Solution:
  31. .................
  32. .#...............
  33. ..##...#.........
  34. ....###.#........
  35. ........#........
  36. ........#........
  37. ........#........
  38. .......#.........
  39. ........#........
  40. ........#..####..
  41. .........##....#.
  42. ...............#.
  43. .................
  44. Process finished with exit code 0

我需要的输出:

  1. Input of Readed File:
  2. 11111111111111111
  3. 10110011000111111
  4. 11001110111001111
  5. 10110001011100111
  6. 11101111011011001
  7. 11101001011011111
  8. 11011011011001011
  9. 10111100111110111
  10. 11011011011111101
  11. 11100111011000011
  12. 10011110100111101
  13. 10100110111111101
  14. 11111111111111111
  15. ROW: 13 COL: 17
  16. Created Maze:
  17. 11111111111111111
  18. 10110011000111111
  19. 11001110111001111
  20. 10110001011100111
  21. 11101111011011001
  22. 11101001011011111
  23. 11011011011001011
  24. 10111100111110111
  25. 11011011011111101
  26. 11100111011000011
  27. 10011110100111101
  28. 10100110111111101
  29. 11111111111111111
  30. Solution 1:
  31. .................
  32. .#...............
  33. ..##...#.........
  34. ....###.#........
  35. ........#........
  36. ........#........
  37. ........#........
  38. .......#.........
  39. ........#........
  40. ........#..####..
  41. .........##....#.
  42. ...............#.
  43. .................
  44. Solution 2:
  45. .................
  46. .#...............
  47. ..##.............
  48. ....#............
  49. ...#.............
  50. ...#.............
  51. ..#..............
  52. .#....##.........
  53. ..#..#..#........
  54. ...##...#..####..
  55. .........##....#.
  56. ...............#.
  57. .................
  58. Process finished with exit code 0
cedebl8k

cedebl8k1#

你想要的结果是'各种各样的解决方案,可以通过(东北,西北)到(东南,西南)',你需要解决使用堆栈?如果是这样的话,我建议您使用两个堆栈,一个用于保存所有的可能性(将所有的toeast、totest等存储在您可以去的地方),另一个用于保存当前的ongoings(每个可能的解决方案,作为缓冲区)
只需添加将当前进程保存在缓冲区中的逻辑,并在它是原始代码上的解决方案时打印路径。如果它不是一个解决方案,并且无法到达(东南、西南),则回溯并恢复缓冲区堆栈。对于这个逻辑,您需要另一个保存堆栈的位置,您最后从不同的方向选择的位置。
总之,

  1. Stack1 => to save all possibilities
  2. Stack2 => current paths. If not a solution, delete and restore
  3. Stack3 => where you chose one direction from many. Need to traceback the path.
  4. Stack2 copies Stack1 whenever you progress,
  5. when reach the goal you print your Stack2 as a solution,
  6. if not, pop until your latest decision informed by popping Stack3.

相关问题