java - 我无法在 java 中修改我的静态变量

Question

你给出一个网格(这里是 4x4)。您需要找出从 (0,0) 到 (4,4) 的唯一路径的总数。 main() 为此调用一个函数 pathify。它找到可能的“下一步”并再次调用它。当到达 (4,4) 时 noOfPaths++；应该执行。这不会发生，我找不到问题所在。

import java.util.ArrayList;

    public class NoOfPaths {
        static int xRows = 4; 
        static int yColumns = 4;
        static int noOfPaths = 0;

        /*A robot is located in the upper-left corner of a 4×4 grid. 
         * The robot can move either up, down, left, or right, 
         * but cannot go to the same location twice. 
         * The robot is trying to reach the lower-right corner of the grid. 
         * Your task is to find out the number of unique ways to reach the destination.
         **/

        static ArrayList validNeighbours (int x,int y, ArrayList visited) {
            ArrayList valid = new ArrayList();

            if((x+1 <= xRows) && !visited.contains(((x+1)*10)+y) ) {
                valid.add(((x+1)*10)+y);
            }
            if((x-1 >= 0) && !visited.contains(((x-1)*10)+y) ) {
                valid.add(((x-1)*10)+y);
            }
            if((y+1 <= yColumns) && !visited.contains(x*10+y+1) ) {
                valid.add(x*10+y+1);
            }
            if((y-1 >= 0) && !visited.contains(x*10+y-1) ) {
                valid.add(x*10+y-1);
            }

            return valid;
        }

        static void pathify(int x,int y,  ArrayList alreadyVisited) {
            if(x == xRows && y == yColumns) {
                noOfPaths++;
            } else {
                alreadyVisited.add(x*10+y);
                ArrayList callAgain = new ArrayList();
                callAgain = validNeighbours(x,y,alreadyVisited);
                for (int t=0,temp; t<callAgain.size(); t++) {
                    temp=(int) callAgain.get(t);
                    pathify(temp/10, temp%10, alreadyVisited);
                }

            }
        }

        public static void main(String[] args) {


            ArrayList alreadyVisited = new ArrayList();

            pathify(0, 0, alreadyVisited);

            System.out.println(noOfPaths);
        }

    }

Answer 1

错误在于您处理alreadyVisited 的方式。第一次调用 pathify 时，此列表将仅包含初始方 block (0,0)，这很好。这是代码的重要部分:

            for (int t=0,temp; t<callAgain.size(); t++) {
                temp=(int) callAgain.get(t);
                pathify(temp/10, temp%10, alreadyVisited);
            }

您已经找到了初始单元格的邻居。您的代码将选择第一个邻居；然后它将找到从该邻居开始的路径，并且对 pathify 的递归调用会将单元格添加到 alreadyVisited。

现在，在所有递归调用返回后，您就可以找到从初始单元格的第二个 邻居开始的单元格。但是你有一个问题:alreadyVisited 仍然有它从它找到的从第二个邻居开始的路径收集的所有单元格。 所以你不会找到所有可能的路径开始于第二个邻居；您不会在您之前找到的任何 路径中找到包含任何 单元格的任何路径。这不是您想要的，因为您只想避免访问每个 路径中的同一个单元格——您不想避免访问所有先前路径中的同一个单元格。 (我稍微简化了一点。实际上，问题将开始出现在递归堆栈的更深处，您甚至找不到从第一个邻居开始的所有路径。)

在实现递归算法时，我发现保留由递归调用共享的中间数据结构通常不是一个好主意，递归调用将被这些调用修改。在本例中，这是列表 alreadyVisited。问题在于，当堆栈深处的调用修改结构时，这会影响更上层的调用，因为它们会在更深层次的调用返回后看到修改，这基本上是它们需要在它们下面更改的数据。 (我不是在谈论用于保存结果列表的集合，如果该列表基本上是只写的。)这里避免它的方法是，而不是添加到 alreadyVisited，您可以创建此列表的克隆，然后添加到其中。这样，更深的调用可以确保它不会通过更改数据来影响较浅的调用。也就是说，而不是

alreadyVisited.add(x*10+y);

写

alreadyVisited = [make a copy of alreadyVisited];
alreadyVisited.add(x*10+y);

add 将修改一个新列表，而不是其他调用正在使用的列表。 (就个人而言，我会声明一个新变量，例如 newAlreadyVisited，因为出于可读性原因，我不太喜欢修改参数。)

这看起来效率不高。它肯定会使用更多内存(尽管内存应该很快就能被垃圾回收)。但是尝试在递归调用之间共享数据结构是非常非常难以正确完成的。如果您非常小心地清理更改并将结构恢复到方法开始时的状态，就可以做到这一点。如果结构类似于一棵大树，那么这可能是必要的，使得每次调用都无法复制。但要使事情顺利进行可能需要很多技巧。

编辑: 我测试了它，它似乎可以工作:12 if xRows=yColumns=2, 8512 if both are 4 (is对吗？)。另一种方法:我没有复制列表，而是尝试了

alreadyVisited.remove((Object)(x*10+y));

在方法的末尾((Object) 是必需的，这样 Java 就不会认为您在索引处删除)，这给了我相同的结果。如果这样做，您将确保 alreadyVisited 在 pathify 返回时与它开始时相同。但我想强调的是，除非您真的知道自己在做什么，否则我不推荐这种“清理”方法。