[数据结构与算法]leetcode 994. Rotting Oranges | 994. 腐烂的橘子（BFS）

题目

https://leetcode.com/problems/rotting-oranges/

题解

和 leetcode 542. 01 Matrix | 542. 01 矩阵（图解，广度优先搜索） 这道题几乎没有区别，直接用 542 的图，来讲一下“感染” 的过程，实际上就是个 BFS

只不过本题的 0,1,2 都被占用了，所以我们用 term=3 开始，标记感染轮数。感染过程中，每一轮 term+1，并且记录每一轮感染的数量 incr。如果某一轮出现 incr=0，即没有任何 orange 被感染，则说明感染过程结束，退出循环。

最后，感染完成后，检查一下矩阵中有没有剩余 1.

class Solution {
    public int orangesRotting(int[][] grid) {
        int M = grid.length;
        int N = grid[0].length;

        int incr = 1; // num of affected in this term
        int term = 3; // 0, 1, 2 already in use, so we mark 'affected' from term=3. term will incr by 1 in each round.
        while (incr > 0) {
            incr = 0;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (grid[i][j] == term - 1) { // grid[i][j] == term - 1 means this coordinate is affected in the last term
                        if (i - 1 >= 0 && grid[i - 1][j] == 1) { // affect left
                            grid[i - 1][j] = term;
                            incr++;
                        }
                        if (i + 1 < M && grid[i + 1][j] == 1) { // affect right
                            grid[i + 1][j] = term;
                            incr++;
                        }
                        if (j - 1 >= 0 && grid[i][j - 1] == 1) { // affect up
                            grid[i][j - 1] = term;
                            incr++;
                        }
                        if (j + 1 < N && grid[i][j + 1] == 1) { // affect down
                            grid[i][j + 1] = term;
                            incr++;
                        }
                    }
                }
            }
            term++;
        }

        // check no 1
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == 1) return -1;
            }
        }
        return term - 4;
    }
}