如何在java中使用2d数组迷宫查找路径

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在附近，它将返回程序。如果没有，则检查起点周围的任何“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，那么它将回溯并返回到起点。然后，它将向东，向西和向南移动。

有人能帮我吗？？thx！@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

当问题被问到时，这个解决方案应该有效：

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(这是算法根据方向优先级选择的路径)。

我认为你从你发布的代码中缺少的主要东西是一种跟踪当前路径并在遇到死胡同时回溯的方法。

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

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

解决这个问题的经典方法是使用另一个数据结构来“着色”顶点，该数据结构表示顶点之前是否访问过。

这个麻省理工开放式课程讲座可能会帮助你找到正确的方向:https://OCW . MIT . edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/presentation-videos/presentation-13-width-first-search-bfs/

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

Answer 3

使用全局变量（标志）确定是否找到了正确的路径。

例如：

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