Leetcode上Rotten Oranges问题中BFS算法没有标记所有节点

Question

我正在研究 rotten oranges problem:

In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

Example 1:

• Input: [[1,1,1],[1,1,0],[0,1,2]]
• Output: 4

我已经实施了 BFS 解决方案。然后在完成 BFS 之后，我启动另一个迭代以确保没有剩下新鲜的橙子，因为如果有剩下的新鲜橙子，那么我必须 return -1.

但是，我发现在最后一个循环中，只有一些值被更改为 2，而其他一些值仍为 1。我不确定为什么它们没有也更改为 2。

class Solution {
    public int orangesRotting(int[][] grid) {
        //need adjacency list/matrix
        Queue<String> q = new LinkedList<>();
        int[] count = new int[1];
        count[0] = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 2) {
                    q.add("" + i + j);
                    bfs(grid, i, j, count, q);
                }
            }
        }
        
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                // does NOT always print correct value: 1 is not changed to 2
                System.out.println(grid[i][j]); 
                if(grid[i][j] == 1) {
                    return -1;  // ... and so this -1 is returned when it shouldn't
                }
            }
        }
        
        return count[0];
    }
    
    private static void bfs(int[][] grid, int i, int j, int[] count,  Queue<String> q) {
        while(!q.isEmpty()) {
            String s = q.remove();
            //System.out.println(s); //prints correct indices
            i = Integer.parseInt(s.substring(0,1));
            j = Integer.parseInt(s.substring(1));
            
            if(i - 1 > 0 && grid[i - 1][j] == 1) {
                count[0]++;
                i--;
                grid[i][j] = 2;
                q.add("" + i + j);
            }
            if(i + 1 < grid.length && grid[i + 1][j] == 1) {
                count[0]++;
                i++;
                grid[i][j] = 2;
                q.add("" + i + j);
            }
            if(j - 1 > 0 && grid[i][j - 1] == 1) {
                count[0]++;
                j--;
                grid[i][j] = 2;
                q.add("" + i + j);
            }
            if(j + 1 < grid.length && grid[i][j + 1] == 1) {
                count[0]++;
                j++;
                grid[i][j] = 2;
                q.add("" + i + j);
            }
        }
        
    }
    
}

对于上面引用的示例，我的代码输出 -1，因为它仍然在最后一个循环中找到 1，而它不应该。

你能帮我弄清楚为什么会这样吗？

Answer 1

几个问题：

• 从不检查第 0 列或第 0 行中的单元格是否感染橙子。当 i 为 1 时，比较 i - 1 > 0 不正确，但您还应该检查 grid[0][j]... j.

  也会出现同样的问题

• 通过将 i 修改为 i--，您会影响下一个 if 条件，这些条件旨在查看 i 的原始值.所以你不应该改变 i 的值（也不改变 j 的值），而是在不修改 i.

  的情况下分配给 grid[i-1][j]

• 在 bfs 中，j 索引被错误地与 grid.length 进行比较。它应该与 grid[i].length 进行比较，因为不能保证网格是正方形的。

• 每 个橙子腐烂，计数就会增加，但这不是应该计数的。许多橘子在 相同的 分钟内会腐烂，您应该只计算分钟数，而不是橘子。要正确计数，您应该进行两项更改：

  • 只有当你收集完队列中所有的烂橘子后才对 bfs 进行初始调用，因为它们都属于第 0 分钟。

  • 在 bfs 函数本身中，将新的烂橙子添加到一个单独的队列中，这样您就知道在这一分钟内添加了哪些烂橙子。然后当原来的队列变空时，将第二个队列移到第一个，占下一分钟，然后重复。

• 没问题，但不需要将 i 和 j 作为参数传递给 bfs，而不是传递对计数器的引用, 让 bfs return 计数.

我已尽量不对您的代码进行超出必要的更改以使其正常工作：

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<String> q = new LinkedList<>();
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 2) {
                    q.add("" + i + j);
                }
            }
        }
        // Only call BFS when all rotten oranges on "minute 0" are identified
        int count = bfs(grid, q);       
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                System.out.println(grid[i][j]); //does NOT print correct value, not changed to 2
                if(grid[i][j] == 1) {
                   return -1;
                }
            }
        }      
        return count;
    }
    
    private static int bfs(int[][] grid, Queue<String> q) {
        int count = 0;
        while(true) { // One iteration per minute
            // Use another queue for the next minute
            Queue<String> q2 = new LinkedList<>();
            // Populate the new queue with oranges that get rotten in this minute
            while(!q.isEmpty()) {
                String s = q.remove();
                int i = Integer.parseInt(s.substring(0,1));
                int j = Integer.parseInt(s.substring(1));
                if(i - 1 >= 0 && grid[i - 1][j] == 1) {
                    // Do not increase the counter for each separate orange!
                    // ...and do not change the value of i or j.
                    grid[i-1][j] = 2;
                    q2.add("" + (i-1) + j);
                }
                if(i + 1 < grid.length && grid[i + 1][j] == 1) {
                    grid[i+1][j] = 2;
                    q2.add("" + (i+1) + j);
                }
                if(j - 1 >= 0 && grid[i][j - 1] == 1) {
                    grid[i][j-1] = 2;
                    q2.add("" + i + (j-1));
                }
                // Compare against the correct length
                if(j + 1 < grid[i].length && grid[i][j + 1] == 1) {
                    grid[i][j+1] = 2;
                    q2.add("" + i + (j+1));
                }
            }
            if (q2.isEmpty()) { // No new oranges were turned rotten
                return count;
            }
            // Continue for a next minute: only now increase the counter
            count++;
            q = q2;
        }
    } 
}

肯定有一些方法可以使 运行 更有效，比如使用数组而不是队列。