递归迷宫算法

Question

递归迷宫算法

4

我正在使用递归解决迷宫问题，我的矩阵如下所示。

char maze[][] = 
    {
        {'#','#','#','#','#','#','#','#','#','#','#'},
        {'#',' ',' ',' ',' ',' ',' ',' ',' ',' ','#'},
        {'#','#','#','#',' ','#','#','#','#','#','#'},
        {'#',' ',' ',' ',' ','#',' ',' ',' ',' ','X'},
        {'#',' ',' ',' ',' ','#',' ',' ',' ',' ','#'},
        {'#',' ','#','#','#','#','#','#',' ','#','#'},
        {'#',' ',' ',' ',' ',' ',' ',' ',' ',' ','#'},
        {'#','#','#','#','#','#','#','#','#','#','#'},

    };

这是更大矩阵的原型。我的递归求解方法如下：

private void solve(int x, int y) {
    // set everything to false
    wasHere = new boolean[maze.length][maze[1].length];
    correctPath = new boolean[maze.length][maze[1].length];
     for (int i = 0; i < maze.length; i++){  
            // Sets boolean Arrays to default values
            for (int j = 0; j < maze[i].length; j++){
                wasHere[i][j] = false;              // set everything to false
                correctPath[i][j] = false;          
            }
     }
boolean b = solveRecursion(1,1);
System.out.println(b);

}

正如您在这里所注意到的，我正在返回一个布尔值。如果我找到了一条路径，它应该给我一个 true。但是它一直给我 false。我不确定我在 solveRecursion 方法中制造了哪些逻辑错误。下面是该方法：

    private boolean solveRecursion(int x, int y) {
        if (x == endX && y == endY){
            return true;
        }
        if (maze[x][y] == '#' || wasHere[x][y]){
            return false;
        }
        wasHere[x][y]=true;
        if (x != 0) // Checks if not on left edge
            if (solveRecursion(x-1, y)) { // Recalls method one to the left
                correctPath[x][y] = true; // Sets that path value to true;
                maze[x][y]='S';
                return true;
            }
        if (x != maze[0].length ) // Checks if not on right edge
                if (solveRecursion(x+1, y)) { // Recalls method one to the right
                    correctPath[x][y] = true;
                    maze[x][y]='S';
                    return true;
            }
        if (y != 0)  // Checks if not on top edge
            if (solveRecursion(x, y-1)) { // Recalls method one up
                correctPath[x][y] = true;
                maze[x][y]='S';
                return true;
           }
        if (y != maze.length) // Checks if not on bottom edge
            if (solveRecursion(x, y+1)) { // Recalls method one down
                correctPath[x][y] = true;
                maze[x][y]='S';
                return true;
            }
        return false;


}

endX =3; endY =10;

- Shadid

2

将调试器附加到solveRecursion的开头并监视发生的调用。然后，您就能够确定“false”发生的时间/位置。 - user2864740

另外，当您调用此代码时："solveRecursion(x-1, y) // Recalls method one to the left"，您实际上并没有调用左侧元素的方法，而是调用了上方元素的方法。 - Tomasz Bekas

@DavidHarkness 如果你指的是矩阵，那么它们不是重复的。第四行末尾有一个“X”，而第五行有一个“#”。我的程序必须到达X。在程序的早期部分，我找出了数组中“X”的位置。现在我正在尝试解决这个数组。我想找到从给定点（1,1）到X位置的最短路径。 - Shadid

正如用户@user286474所提到的，当您的矩阵不是很大时，请使用调试器来解决问题。 - Tomasz Bekas

@user3422137 啊是的，我现在明白了。 - David Harkness

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- leigero · Accepted Answer

您可能将网格的坐标系搞混了。在您的情况下，X表示行数，而Y表示列数。

您正在检查是否 y != maze.length，如果是，则向“下”移动一步，实际上是向右移动一步，而不是向下移动一步。

这种混淆使得您的Y坐标受到X值的限制。

您应该将那一行改为：

 if (y != maze[0].length)

那样就解决了问题。目前你永远无法到达值为 (3,9) 的位置，因为你的 if 语句检查的是坐标为 (8,9) 并且是这样说的：

 if (y != maze.length) // Hmm. my coordinates are (8,9) so y = 9. 
                       // maze.length is 9, so this is false.

边缘值从不被考虑。