java - 如何在java中使用二维数组迷宫找到路径

Question

B B B B B

B B B O B

B B S O B

B O O B B

B B X B B

这里，

S = 起点(2,2)

B = block

O = 打开

X = 退出

我想制作一个可以检查东、西、北、南的迷宫。如果 X 在附近，它将返回该程序。如果没有，则检查起点周围是否有“O”，并递归地传递新的起点。如果无路可走并且没有找到“X”，它将回到原来的起点(2,2)并检查西、东、南。

程序结束后，我得到:

B B B B B

B B B + B

B B + + B

B O + B B

B B X B B

但是，我期望递归后的输出是:

B B B B B

B B B - B

B B + - B

B O + B B

B B X B B

这是我现在的代码:

public static void Find_Path(char[][] maze, int startX, int startY){
int x[] = { -1, 0, 0, 1};
int y[] = {0,-1,1,0};
boolean found = false;
maze[startX][startY] = '+';
for(int i = 0; i < 4 ; i++){// check if there are 'X' around the S.
  int afterX = x[i] + startX;
  int afterY = y[i] + startY;
  if(maze[afterX][afterY] == 'X'){// if yesy, return.
    found = true;
    return;
  }
}

for(int i = 0; i < 4 ; i++){// if no, check for 'O'
  int afterX = x[i] + startX;
  int afterY = y[i] + startY;
  if(maze[afterX][afterY] == 'O'){
    Find_Path(maze, afterX, afterY);
    if(!found){
     maze[afterX][afterY] = '-';
  }
 }
}

startX和startY是起点的索引。

我不知道如何把错误的路径转“-”。程序会先检查北，如果顶部是B，那么它会回溯并回到起点。然后，它会向东、向西、向南移动。

谁能帮帮我吗？谢谢!@蒙塔西尔

BBBBB
BBOOB
XOBOB
BSOBB
BBBBB

BBBBB
BBOOB
X+BOB ( It should stop right here, because there is X around it.)
BSOBB
BBBBB

BBBBB
BBOOB
X+BOB (but, somehow it go to the right of the startpoint and mark the 'O' to  '+'
BS+BB
BBBBB

Answer 1

使用全局变量(标志)来确定您是否找到了正确的路径。

例如:

public class YourClass{
    static boolean found = false; // the global flag
    // your existing code

    public static void Find_Path(char[][] maze, int startX, int startY){
        // ....
        for(int i = 0; i < 4 ; i++){
            // ...
            if(maze[afterX][afterY] == 'X'){
                found = true; // path found
                return;
            }
        }
        for(int i = 0; i < 4 ; i++){
            // ...
            if(found) // path already found in earlier recursive call; no need to search anymore
                return;
            else{ // path not found yet, have to continue searching
                if(maze[afterX][afterY] == 'O'){
                    Find_Path(maze, afterX, afterY);
                    if(!found){ // path not found
                        maze[afterX][afterY] = '-';
                    }
                }
            }
        }
    }
}