首页 文章

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

提问于
浏览 次
1
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，那么它将回溯并返回起点 . 然后，它会向东，西，南 .

谁能帮我吗？？谢谢！ @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
java recursion flood-fill

3 回答

  • 0

    您正在寻找的算法称为广度优先搜索和深度优先搜索 . 如果你的迷宫中存在一个循环，你将遇到的一个问题 . 例如，如果你有这个怎么办？

    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/lecture-videos/lecture-13-breadth-first-search-bfs/

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

    回复于
  • 0

    问题是这个解决方案应该工作：

    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]

    关于这个解决方案和解决问题的方法有一点需要注意： This won't provide the shortest path to the exit

    该解决方案按此顺序优先：东，西，南，北 .

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

    开始迷宫：

    {'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（这个算法因为方向优先而选择的路径） .

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

    回复于
  • 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] = '-';
                    }
                }
            }
        }
    }
}
    回复于

相关问题