递归遍历 2D 数组解决迷宫时出现 ArrayIndexOutOfBoundsException

Question

我需要编写一个方法来解决迷宫（二维数组）。我需要始终保持在墙的正左侧，当我到达出口点（始终位于同一位置）或没有可能的解决方案时（并且在穿过迷宫后），我的方法应该结束，我又回到了入口点）。

我能够做到这一切，没有问题，我可以直观地确保它正在做我想要它做的事情（我们从我们的讲师那里得到了一些输出视觉效果的其他方法），并且我的控制台调试输出是正确的好吧。

这是相关代码：

public static void main(String[] args) {
    maze = generateMaze(10,10);
    walk(1,0,0);
}

public static void walk(int x, int y, int direction) {
    System.out.println("x = " + x + " y = " + y); //debug output
    draw(x,y,maze); //draws current position
    if (x == maze.length-1 && y == maze[1].length-2) { //terminate when reached exit
        System.out.println("Geschafft!");
        return;
    }
    if (x == 1 && y == 0 && direction == 3) { //terminate when at starting point again (no solution)
        System.out.println("Keine Lösung möglich.");
        return;
    }
    if (direction == 0) { //go down
        if (maze [x][y+1]) {
            walk(x,y,1);
        }
        walk(x,y+1,2);
    }
    if (direction == 1) { //go right
        if(maze [x+1][y]) {
            walk(x,y,3);
        }
        walk(x+1,y,0);
    }
    if (direction == 2) { //go left
        if(maze [x-1][y]) {
            walk(x,y,0);
        }
        walk(x-1,y,3);
    }
    if (direction == 3) { //go up
        if(maze[x][y-1]) {
            walk(x,y,2);
        }
        walk(x,y-1,1);
    }    
}

只有一个问题：如何正确结束递归？这是我从控制台得到的：

x = 1 y = 0
x = 1 y = 1
x = 1 y = 1
x = 1 y = 2
and so on...
x = 8 y = 8
x = 9 y = 8
Geschafft!
x = 8 y = 9
x = 8 y = 9
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at maze.MazeSolution.walk(MazeSolution.java:26)
at maze.MazeSolution.walk(MazeSolution.java:39)
and some more of that

我确实理解这个错误，递归显然没有在我想要的地方结束，并且

x

或

y

增加并尝试使用数组中不存在的索引。

当这两种情况之一成立时，为什么递归不以 return 语句结束：

if (x == maze.length-1 && y == maze[1].length-2) { //terminate when reached exit
    System.out.println("Geschafft!");
    return;
}
if (x == 1 && y == 0 && direction == 3) { //terminate when at starting point again (no solution)
    System.out.println("Keine Lösung möglich.");
    return;
} 

我需要做什么才能正确结束它？

Answer 1

添加到开头

public static void walk(int x, int y, int direction) {
  System.out.println("x = " + x + " y = " + y); //debug output
  if (x >= 10 ||  x < 0 || y >= 10 || y < 0) return;

Answer 2

查看您的退货以及您可能返回的地方。 您可以在包含其他调用的封闭函数的中间返回，而无需警卫来确保它们不被调用。

我建议重新实现你的逻辑；考虑使用 if/else 对来确保互斥。

Answer 3

为什么不简单地返回 true 或 false 并对其做出反应？

所以基本上你添加到你的两个结束案例

return true;

代码就结束了。

if(walk(...)) return true;