leetcode 问题的 BFS 实现在一个测试用例中失败了

Question

我正在尝试用 BFS 方法解决 LeetCode 问题（1219.具有最大黄金的路径）

声明：

在大小为 m x n 的金矿网格中，该矿井中的每个单元格都有一个代表该单元格中黄金数量的整数，如果为空则为 0。 在以下条件下返还您可以收集的最大金币数量： 每次您位于一个牢房中时，您都会收集该牢房中的所有黄金。 从您的位置开始，您可以向左、向右、向上或向下走一步。 您不能多次访问同一个牢房。 切勿访问金币为 0 的单元格。 您可以从网格中任何有黄金的位置开始和停止收集黄金。

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;
    }
}

我能够执行 28 个测试用例，下面的测试用例失败了

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 我在我的代码中找不到问题。任何人都可以帮助找到上述代码的问题

Answer 1

我认为问题是你的

isVis

数组是全局的，而它需要位于你当前正在探索的路径的本地。

考虑一个简单的 2x2 网格

{{1,1}, {1,1}}

。我怀疑你的代码会返回

3

，而正确的答案是

4

。这是因为您将从

0,0

开始，然后检查前往

1,0

的路径和前往

0,1

的路径。但因为

isVis

是全局的，所以两条路径都不允许到达另一条路径访问过的单元格。因此，人们会得到

1,1

，但无法超越它。