递归回溯返回更新值

Question

我正在创建一个递归导航迷宫的程序。代码：

public static boolean traverse(int maze[][], coordinate start)
{
    //recursion: traverse(maze, updated coordinates)

    if(maze[start.y+1][start.x] == 2 || maze[start.y-1][start.x] == 2 || maze[start.y][start.x+1] == 2 || maze[start.y][start.x - 1] == 2)
    {
        display(maze);
        System.out.println("DONE");
        return true;
    }

    else 
    {
        if(north(maze, start) == true)
        {
            maze[start.y-1][start.x] = 4;
            display(maze);
            coordinate temp = start; 
            temp.y--;
            if (traverse(maze, temp) == false)
            {
                maze[start.y][start.x] = 3;

            }
        }   

        if(west(maze, start) == true)
        {
            maze[start.y][start.x-1] = 4;
            display(maze);
            coordinate temp = start;
            temp.x--;
            if (traverse(maze, temp) == false)
            {
                maze[start.y][start.x] = 3;
            }
        }


        if(south(maze, start) == true)
        {
            maze[start.y+1][start.x] = 4;
            display(maze);
            coordinate temp = start;
            temp.y++;
            if (traverse(maze, temp) == false)
            {
                maze[start.y][start.x] = 3;
            }
        }

        if(east(maze, start) == true)
        {
            maze[start.y][start.x+1] = 4;
            display(maze);
            coordinate temp = start;
            temp.x++;
            if (traverse(maze, temp) == false)
            {
                maze[start.y][start.x] = 3;
            }
        }   


    }

    return false;
}

然而，每当我到达死胡同时，它都不会回溯。当我调试时，它表明当程序从递归或“回溯”返回时，我的起始值专注于停留在我的死胡同空间。

例如:

1 1 1 1 1 
1 4 4 4 1 
1 9 1 4 1 
1 1 1 4 1 
1 4 4 4 1 
1 4 1 0 1 
1 4 1 0 1 
1 1 1 2 1  

9是我的出发点。2是我的退出。4是我的道路。1 表示墙壁。当我到达一个死胡同时（在本例中为第 7 行，第 2 列）。我的立场是等于整个程序其余部分的死胡同空间。这是为什么呢？

Answer 1

你可以缩短很多。试试他的代码。

public static boolean traverse(int[][] maze, int x, int y) {
    if(y >= maze.length || x >= maze[y].length) return false;
    int value = maze[y][x];
    if(value == 2) {
        display(maze);
        System.out.println("DONE");
        return true;
    } else if(value == 0 || value == 9) {
        maze[y][x] = 4;
        boolean success = false;
        loop:
        for(int dy = -1; dy <= 1; dy++) {
            for(int dx = -1; dx <= 1; dx++) {
                if(dx == 0 && dy == 0 ||
                   dx != 0 && dy != 0) continue;
                success |= traverse(maze, x + dx, y + dy);
                if(success) break loop;
            }
        }
        maze[y][x] = value;
        return success;
    }
    return false;
}

public static void main(String[] args) {
    int[][] maze = {{1, 1, 1, 1, 1}, 
                    {1, 0, 0, 0, 1},
                    {1, 9, 1, 0, 1},
                    {1, 1, 1, 0, 1},
                    {1, 0, 0, 0, 1},
                    {1, 0, 1, 0, 1},
                    {1, 0, 1, 0, 1},
                    {1, 1, 1, 2, 1}};
    int x = 0, y = 0;
    loop:
    for(y = 0; y < maze.length; y++) {
        for(x = 0; x < maze[y].length; x++) {
            if(maze[y][x] == 9) break loop;
        }
    }
    boolean success = traverse(maze, x, y);
    System.out.println();
    System.out.println(success);
    display(maze);
}

Answer 2

当您向上移动堆栈时，值会更新并且永远不会“回溯”，因为它们不会在每个级别中保留其原始值，回溯基本上是在树中行走，如果每个节点在每个级别更新时不保留原始值，则每个节点都将具有叶节点的值，当叶子节点得到满足时， 节点不记得它们的原始值。相反，您需要在向上遍历堆栈时传递一个新值，而无需更新每个堆栈，以记住它们被其父级调用时所拥有的内容。

最简单的方法是尝试，

 traverse(int maze[][], int x , int y)

您的后续呼叫将如下所示

 if(north(maze, x , y) == true)
    {
        maze[y-1][x] = 4;
        display(maze);

        //temp.y--;
        if (traverse(maze, x , y-1) == false)
        {
            maze[y][x] = 3;

        }
    }

或者你可以在返回当前堆栈后重置你的值，

我还没有检查你的代码的其余部分，但这可能是代码不回溯的原因