java - 找到从左上角到右下角的所有路径问题。以数组为参数的递归解法输出说明

Question

我有一个 NxN 矩阵，我想找到从左上角到右下角的所有路径，前提是只允许向下和向右移动。

我构建了一个类 Point 来保存矩阵中的坐标。

class Point
{
    public int x, y;

    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString()
    {
        return "(" + this.x + "," + this.y + ")";
    }
}

该算法是递归的，并检查每个点的所有可能移动。

public static void findPath(int grid[][], Point start, Point end, ArrayList<Point> currentPath)
{
        currentPath.add(start);

        if(start.x == end.x && start.y == end.y)
        {
            System.out.println(currentPath);
            return;
        }

        if(start.x + 1 < grid.length)
        {
            findPath(grid, new Point(start.x + 1, start.y), end, currentPath);
        }

        if(start.y + 1 < grid[0].length)
        {
            findPath(grid, new Point(start.x, start.y + 1), end, currentPath);
        }

}

对于一个简单的 2x2 矩阵，我得到以下输出:

[(0,0), (1,0), (1,1)]
[(0,0), (1,0), (1,1), (0,1), (1,1)]

预期的输出是:

[(0,0), (1,0), (1,1)]
[(0,0), (0,1), (1,1)]

看起来在点 (1,0), (1,1) 被弹出堆栈后，堆栈帧中的变量 currentPath 与点 (0,0) 也包含点 (1,0) , (1,1) 来自之前的栈帧。

我主要对这种行为的解释感兴趣，因为互联网上有很多资源可以解决这个问题。这是否与 currentPath 分配在堆上并且只有指向该地址的指针存储在堆栈上这一事实有关？

谢谢。

Answer 1

currentPath 局部变量只引用了一个 ArrayList 实例，因此当您将该变量传递给递归调用时，您传递的是同一个实例。

由于您只是向该 ArrayList 添加元素，因此永远不会删除之前添加的任何元素，因此您可以在示例中看到两条路径的点。

您应该从 ArrayList 中删除您添加的每个点，或者您可以将 ArrayList 的副本传递给每个递归调用:

public static void findPath(int grid[][], Point000 start, Point000 end, ArrayList<Point000> currentPath)
{
    currentPath.add(start);

    if(start.x == end.x && start.y == end.y)
    {
        System.out.println(currentPath);
        return;
    }

    if(start.x + 1 < grid.length)
    {
        findPath(grid, new Point000(start.x + 1, start.y), end, new ArrayList<>(currentPath));
    }

    if(start.y + 1 < grid[0].length)
    {
        findPath(grid, new Point000(start.x, start.y + 1), end, new ArrayList<>(currentPath));
    }

}

现在输出将是:

[(0,0), (1,0), (1,1)]
[(0,0), (0,1), (1,1)]