1

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

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 列）。我的位置将等于整个程序其余部分的死胡同。为什么？

4

2 回答 2

0

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

最简单的方法是尝试，

 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;

        }
    }

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

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

于 2013-10-03T00:05:59.723 回答
0

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

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);
}
于 2013-10-03T00:36:44.820 回答