你给出一个网格(这里是 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);
}
}
最佳答案
错误在于您处理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
返回时与它开始时相同。但我想强调的是,除非您真的知道自己在做什么,否则我不推荐这种“清理”方法。
关于java - 我无法在 java 中修改我的静态变量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41584627/