LeetCode 1219题BFS解法未通过测试用例，求问题排查

问题背景 #

LeetCode 1219. Path with Maximum Gold（最大黄金路径）要求在m×n的金矿网格中，找出可收集的最大黄金量，规则如下：

• 每次到达单元格时收集所有黄金
• 可向上下左右移动一格
• 不可重复访问同一单元格
• 不能访问黄金量为0的单元格
• 可从任意含黄金的位置开始和停止收集

用户尝试用BFS实现，但在测试用例int grid[][] = {{1,0,7,0,0,0},{2,0,6,0,1,0},{3,5,6,7,4,2},{4,3,1,0,2,0},{3,0,5,0,20,0}}上失败，预期结果60，代码输出54。

用户实现的Java代码 #

class Solution {
    public int getMaximumGold(int[][] grid) {
        int max = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 0) {
                    boolean isVis[][] = new boolean[grid.length][grid[0].length];
                    int val = bfs(i, j, isVis, grid);
                    max = Math.max(max, val);
                }
            }
        }
        return max;
    }

    public int bfs(int r, int c, boolean isVis[][], int[][] grid) {
        Queue<int[]> q = new LinkedList<>();

        q.add(new int[] { r, c, grid[r][c] });
        int max = grid[r][c];

        isVis[r][c] = true;

        while (!q.isEmpty()) {
            int path[] = q.poll();

            int[][] arr = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

            for (int i = 0; i < 4; i++) {
                int rc = path[0] + arr[i][0];
                int cc = path[1] + arr[i][1];

                if (rc < 0 || cc < 0 || rc >= grid.length || cc >= grid[0].length || isVis[rc][cc]
                        || grid[rc][cc] == 0) {
                    max = Math.max(max, path[2]);
                    continue;
                }

                int sum = grid[rc][cc] + path[2];
                isVis[rc][cc] = true;

                q.add(new int[] { rc, cc, sum });
            }
        }
        return max;
    }
}

问题根源 #

你的BFS解法存在核心逻辑错误：共享的isVis数组会被不同路径污染。

BFS队列中存储的是不同的路径分支，但你使用的是全局的isVis数组——当某条路径标记了某个单元格为已访问后，其他路径分支就无法再访问这个单元格，这会导致你错过更优的路径。

比如在测试用例中，最优路径需要访问20所在的单元格，但你的代码中可能因为某条提前的路径标记了中间某个关键单元格为已访问，导致无法走到20，从而得到更小的总和54，而非预期的60。

BFS适合分层遍历，但这类需要回溯、探索所有可能路径的问题，更适合用DFS（深度优先搜索）+ 回溯的方式，因为DFS可以在探索完一条路径后，撤销对单元格的访问标记，让其他路径能重新使用该单元格。

修正方案：DFS+回溯 #

将BFS替换为DFS，每次递归访问单元格后，标记为已访问，递归结束后再撤销标记，确保所有路径都能被完整探索：

class Solution {
    private int maxGold = 0;
    private int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}};

    public int getMaximumGold(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    dfs(grid, i, j, 0);
                }
            }
        }
        return maxGold;
    }

    private void dfs(int[][] grid, int r, int c, int currentGold) {
        int m = grid.length;
        int n = grid[0].length;

        // 边界判断：越界、0单元格、已被访问（通过修改grid值标记）
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == 0) {
            maxGold = Math.max(maxGold, currentGold);
            return;
        }

        // 保存当前单元格的黄金值，然后标记为0（表示已访问）
        int gold = grid[r][c];
        grid[r][c] = 0;

        // 递归探索四个方向
        for (int[] dir : directions) {
            dfs(grid, r + dir[0], c + dir[1], currentGold + gold);
        }

        // 回溯：恢复单元格的黄金值
        grid[r][c] = gold;
    }
}

修正逻辑说明 #

• 回溯标记：通过修改grid单元格的值为0来标记已访问，递归结束后恢复原值，避免使用额外的isVis数组，同时确保不同路径之间不会互相干扰。
• DFS探索：每次递归深入一条路径，直到无法继续，此时更新最大黄金量，确保所有可能的路径都被探索到。
• 全局最大值：用成员变量maxGold记录所有路径中的最大值，无需在每个起点单独计算。

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