当我调用使用递归方法找到到达矩阵右下角的所有路径的函数时,它会将访问的路径更新为-1,这样它就不会循环,但在Java中,如果我们一次更新数组它将值更新为 -1 并采取其他可能性。
所以我需要一个Java程序的解决方案来更新原始数组。
package other;
public class Reach_end {
public static void main(String[] args) {
int[][] path = {
{1, 0, 0, 0},
{1, 0, 1, 1},
{1, 1, 1, 1},
{1, 0, 1, 1},
};
System.out.println(pathFinder(path, 0, 0));
}
private static int pathFinder(int[][] path, int row, int col) {
path[row][col] = -1;
int temp = 0;
if (row == path.length-1 && col == path.length-1) {
System.out.println("path found");
return 1;
}
if (row+1 < path.length && path[row+1][col] == 1) {
System.out.println("Moved down " + (row+1) +" " + col);
temp = pathFinder(path, row+1, col);
if (temp >= 1) {
return temp+1;
}
}
temp = 0;
if (col+1 < path.length && path[row][col+1] == 1) {
System.out.println("Moved right " + row + " " + (col+1));
temp = pathFinder(path, row, col+1);
if (temp >= 1) {
return temp+1;
}
}
temp = 0;
if (row-1 >= 0 && path[row-1][col] == 1) {
System.out.println("Moved up " + (row-1) + " " + col);
temp = pathFinder(path, row-1, col);
if (temp >= 1) {
return temp+1;
}
}
temp = 0;
if (col-1 >= 0 && path[row][col-1] == 1) {
System.out.println("Moved left" + (row) + " " + (col-1));
temp = pathFinder(path, row, col-1);
if (temp >= 1) {
return temp+1;
}
}
return 0;
}
}
我需要一个防止数组更新的解决方案。
您可以在覆盖之前保存该值,然后在返回之前将其放回去。
private static int pathFinder(int[][] path, int row, int col) {
int saved = path[row][col];
path[row][col] = -1;
// ...
if (row+1 < path.length && path[row+1][col] == 1) {
System.out.println("Moved down " + (row+1) +" " + col);
temp = pathFinder(path, row+1, col);
if (temp >= 1) {
path[row][col] = saved;
return temp+1;
}
}
// etc, make sure to cover all the returns