Java递归查找矩阵所有路径时避免修改原数组的方案

你遇到的问题核心是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},
        };
        // 创建与原矩阵同尺寸的访问标记矩阵，初始全为未访问
        boolean[][] visited = new boolean[path.length][path[0].length];
        System.out.println(pathFinder(path, visited, 0, 0));
    }

    private static int pathFinder(int[][] path, boolean[][] visited, int row, int col) {
        // 前置判断：越界、当前位置不可走、已访问过，直接返回0
        if (row < 0 || row >= path.length || col < 0 || col >= path[0].length 
            || path[row][col] != 1 || visited[row][col]) {
            return 0;
        }

        // 标记当前位置为已访问
        visited[row][col] = true;

        // 到达终点，记录路径并回溯
        if (row == path.length - 1 && col == path[0].length - 1) {
            System.out.println("path found");
            visited[row][col] = false;
            return 1;
        }

        int totalPaths = 0;
        // 遍历四个方向
        totalPaths += pathFinder(path, visited, row+1, col); // 下
        totalPaths += pathFinder(path, visited, row, col+1); // 右
        totalPaths += pathFinder(path, visited, row-1, col); // 上
        totalPaths += pathFinder(path, visited, row, col-1); // 左

        // 回溯：取消当前位置的访问标记，让其他分支可以访问
        visited[row][col] = false;

        return totalPaths;
    }
}

关键细节说明 #

• 原数组零修改：原path矩阵仅用于判断位置是否可通行（值为1表示允许通过），全程保持初始状态。
• 回溯机制：递归返回前重置当前位置的访问标记，确保其他分支遍历到该位置时不受之前分支的影响。
• 路径统计：修改后的代码会返回所有可行路径的总数，若你需要统计单条路径的长度，只需调整返回值逻辑即可。
• 效率优化：使用布尔矩阵做访问标记比用字符串存储坐标的方式效率更高，内存开销也更小。

内容的提问来源于stack exchange，提问作者Kathiresh P