java - 迷宫递归解决StackOverflow报错

Question

我正在尝试使用递归解决迷宫问题。它被声明为Cell [][] maze。

public class Cell {
    private Wall left;
    private Wall right;
    private Wall up;
    private Wall down;
    private boolean end;

    // Setters and getters not shown
}

如果单元格的某侧没有 Wall，则它的值为 null，否则它引用 Wall 对象。 Wall 引用是一致的:与单个墙相邻的两个单元格都使用适当的字段引用它。如果缺少一面墙，则两个相邻单元格都有相应的 null 条目。这是搜索:

public boolean solveMaze(Cell[][] maze, int i, int j) {

    if (maze[i][j].isEnd()){
        System.out.println(maze[i][j].toString());
        return true;
    }
    if (maze[i][j].getDown() == null) {
        return solveMaze(maze, i, j + 1); 
    }
    if (maze[i][j].getUp() == null) {
        return solveMaze(maze, i, j - 1) ;
    }
    if (maze[i][j].getLeft() == null) {
        return solveMaze(maze, i - 1, j);
    }
    if (maze[i][j].getRight() == null) {
        return solveMaze(maze, i + 1, j) ;  
    }
    return false;
}

我遇到了 Stack Overflow 错误。我的递归停止条件有什么问题？

更新:

在您高度赞赏的帮助下，我解决了这个问题:这是完美无瑕的正确解决方案:

public boolean solveMaze(Cell[][] maze, int i, int j){

    if (maze[i][j].isEnd()){
        System.out.println("Maze Exit :["+i+","+j+"]" );
        return true;
    }

    if (maze[i][j].isVisited()){
        return false;
    }

    maze[i][j].setVisited(true);

    if ((maze[i][j].getButtom() == null) ){
        if (solveMaze(maze,i,j+1)==true)
            return true;
    }

    if ((maze[i][j].getUp() == null) ){
    if ( solveMaze(maze,i,j-1) ==true )
        return true;
    }

    if ((maze[i][j].getLeft() == null)){
        if (solveMaze(maze,i-1,j))
            return true;
    }

    if ((maze[i][j].getRight() == null)){
        if (solveMaze(maze,i+1,j)) 
            return true;
    }

    maze[i][j].setVisited(false);
    return false;
} 

可能对 future 的任何机构都有帮助。

Answer 1

如果迷宫有一个循环，求解器可以永远围绕这个循环运行，这将导致您看到的堆栈溢出。您需要一种方法来确定您何时看到已经看到的迷宫方 block 。在这种情况下，您应该立即回溯。

这可以通过在每个单元格中初始设置为 false 然后为搜索的每个方 block 设置为 true 的 boolean 标志 visited 来完成，或者您可以维护一个单独的 Set 已搜索的 (i,j) 对，最初为空。

注意:您对 i 和 j 的使用是非常规的。如果其他人用常规用法编写了迷宫阅读代码，这可能会导致问题。在数学中，i 通常用于行号，j 用于列。使用此约定，您的墙壁测试与您的增量和减量不一致。例如，缺少底壁需要您增加 i。