在java递归中查找所有可能的路径

Question

当我调用使用递归方法找到到达矩阵右下角的所有路径的函数时，它会将访问的路径更新为-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;
    }

}

我需要一个防止数组更新的解决方案

Answer 1

您可以在覆盖之前保存该值，然后在返回之前将其放回去。

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