如何在 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 = 块

O = 打开

X = 退出

我想制作一个可以检查东西南北的迷宫。如果 X 在附近，它将 return 程序。如果不是，则检查起点周围是否有任何 '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 那么它将回溯并返回到起点。然后，它会向东，向西，向南。

谁能帮帮我？？谢谢！ @Muntasir

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] = '-';
                    }
                }
            }
        }
    }
}

Answer 2

您要查找的算法称为广度优先搜索和深度优先搜索。您将运行遇到的一个问题是您的迷宫中是否存在循环。例如，如果你有这个会怎样？

B B B B B
B O O O B
B O S O B
B O O O B
B B B B B

那么算法可能会陷入无法逃脱的循环。

解决这个问题的经典方法是"color"顶点使用另一种数据结构来表示顶点之前是否被访问过。

这个 MIT OCW 讲座可能会帮助您指明正确的方向：https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-13-breadth-first-search-bfs/

不过，要直接回答您的问题，请考虑基本情况。当你找到 X 时，是什么阻止了循环的搅动和转动？在目前的状态下，看起来唯一能阻止 iteration/recursion 的就是你运行没地方看了。您需要某种变量来告诉第二个 for 循环停止搜索。

Answer 3

如问题所问，此解决方案应该有效：

import java.util.Arrays;

public class TwoDSolver {

private char[][] maze;
private String currPath;
private int currX;
private int currY;
private boolean unsolvable;

public static void main(String[] args) {
    char[][] customMaze = {
            {'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'}
    };

    String startPath = "";
    int startX = 2;
    int startY = 2;
    TwoDSolver solver = new TwoDSolver(customMaze, startX, startY, startPath, false);
    // place a plus at the start point
    solver.placePlus();
    solver.solveMaze();
    if (solver.unsolvable) {
        System.out.println("The maze is unsolvable");
    } else {
        System.out.println("Solved, A correct path is: " + solver.currPath);
    }
    solver.printMaze();


}

// constructor
TwoDSolver(char[][]aMaze, int stX, int stY, String currentPath, boolean noSolution) {
    maze = aMaze;
    currX = stX;
    currY = stY;
    currPath = currentPath;
    unsolvable = noSolution;
}

// indicate taken path
void placePlus() {
    maze[currX][currY] = '+';
}

// for backtracking
void placeMinus() {
    maze[currX][currY] = '-';
}

// solve
// priority in this order East, West, South, North
void solveMaze() {
    // check for a win
    if (checkForWin()) {
        return;
    }
    // No win, so let's check for an opening
    // check east
    if (currY + 1 < maze[currX].length && checkForOpen(currX, currY + 1)) {
        currY++;
        placePlus();
        currPath += "E"; // Append East to our current path
        // recursive call continue searching
        solveMaze();
        // check west
    } else if (currY - 1 >= 0 && checkForOpen(currX, currY - 1)) {
        currY--;
        placePlus();
        currPath += "W";
        solveMaze();
        // check south
    }  else if (currX + 1 < maze.length && checkForOpen(currX + 1, currY)) {
        currX++;
        placePlus();
        currPath += "S";
        solveMaze();
        // check north
    }  else if (currX - 1 >= 0 && checkForOpen(currX - 1, currY)) {
        currX--;
        placePlus();
        currPath += "N";
        solveMaze();
    } else { // we've hit a dead end, we need to backtrack
        if (currPath.length() == 0) {
            // we're back at the starting point, the maze is unsolvable
            unsolvable = true;
            return;
        } else {
            // we've reached a dead end, lets backtrack
            placeMinus();
            backTrack();
        }
    }
}

// see if the spot at a give x, y is open
boolean checkForOpen(int x, int y) {
    return maze[x][y] == 'O';
}

// see if any of the surrounding spots are the exit
boolean checkForWin() {
    // make sure to protect against out of bounds as well
    return ((currY + 1 < maze[currX].length && maze[currX][currY + 1] == 'X') ||
            (currY - 1 >= 0  && maze[currX][currY - 1] == 'X') ||
            (currX + 1 < maze[currX].length && maze[currX + 1][currY] == 'X') ||
            (currX -1 >= 0 && maze[currX -1][currY] == 'X'));
}

void backTrack() {
    // sanity chek currPath.length() should always be > 0 when we call backTrack
    if (currPath.length() > 0) {
        placeMinus();
        switch (currPath.charAt(currPath.length() - 1)) {
        case 'E':
            currY--;
            break;
        case 'W':
            currY++;
            break;
        case 'S':
            currX--;
            break;
        case 'N':
            currX++;
            break;
        }
        currPath = currPath.substring(0, currPath.length()-1);
        solveMaze();    
    }
}

void printMaze() {
    for (int i = 0; i < maze.length; i++) {
        System.out.println(Arrays.toString(maze[i]));
    }
}

}

对于您的示例迷宫，输出为：

Solved, A correct path is: S
[B, B, B, B, B]
[B, B, B, -, B]
[B, B, +, -, B]
[B, O, +, B, B]
[B, B, X, B, B]

对于@William John Howard 设计的无解迷宫示例：

{'B', 'B', 'B', 'B', 'B'},
{'B', 'O', 'O', 'O', 'B'},
{'B', 'O', 'S', 'O', 'B'},
{'B', 'O', 'O', 'O', 'B'},
{'B', 'B', 'B', 'B', 'B'}

输出为：

The maze is unsolvable
[B, B, B, B, B]
[B, -, -, -, B]
[B, -, +, -, B]
[B, -, -, -, B]
[B, B, B, B, B]

关于此解决方案和这种解决问题的方式需要注意的一件事： 这不会提供到出口的最短路径

此解决方案的优先顺序为：东、西、南、北。

这是我的意思的一个例子：

起始迷宫：

{'B', 'B', 'B', 'X', 'B'},
{'B', 'O', 'O', 'O', 'B'},
{'B', 'O', 'S', 'O', 'B'},
{'B', 'O', 'O', 'O', 'B'},
{'B', 'B', 'B', 'B', 'B'}

输出：

Solved, A correct path is: ESWWNNEE
[B, B, B, X, B]
[B, +, +, +, B]
[B, +, +, +, B]
[B, +, +, +, B]
[B, B, B, B, B]

如您所见，有多个通往出口的正确路径，NE、EN、WNEE、SENN、SWNNEE、ESWWNNEE（此算法选择的路径是因为方向优先）。

我认为您发布的代码中缺少的主要内容是跟踪当前路径并在遇到死胡同时回溯的方法。

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

How do I find path using 2d array maze in java

java

recursion

flood-fill