[LeetCode] 994. Rotting Oranges

You are given an m x n grid where each cell can have one of three values:

0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent 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.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1, or 2.

腐烂的橘子。

在给定的网格中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotting-oranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目说了是求每个烂橘子四周围的情况，所以思路也是 flood fill 类型的 BFS。这个题跟一般的 BFS 的题目不太一样的地方在于，需要考虑会不会有一直有好橘子不腐烂的情况，所以需要算一下一共有多少个好橘子 count，每次腐烂了需要减去；和需要记录遍历次数 round，因为这是需要返回的参数。

先遍历一遍 input，得到好橘子的个数 count，也将所有的坏橘子的坐标加入 queue。从 queue 中弹出的时候，判断每个坐标的上下左右是否有好橘子，若有，则把他标记为坏橘子，再放回 queue。while 循环跳出的条件是 count == 0 或者 queue 为空。最后判断如果 count 不为 0 则返回 -1，说明一直有好橘子存在；否则则返回轮数 round。

时间O(mn)

空间O(mn)

Java BFS实现一

 1 class Solution {
 2     public int orangesRotting(int[][] grid) {
 3         int M = grid.length;
 4         int N = grid[0].length;
 5         Queue<int[]> queue = new LinkedList<>();
 6         int count = 0;
 7         for (int i = 0; i < M; i++) {
 8             for (int j = 0; j < N; j++) {
 9                 if (grid[i][j] == 1) {
10                     count++;
11                 } else if (grid[i][j] == 2) {
12                     queue.offer(new int[] { i, j });
13                 }
14             }
15         }
16 
17         int round = 0;
18         while (count > 0 && !queue.isEmpty()) {
19             round++;
20             int n = queue.size();
21             for (int i = 0; i < n; i++) {
22                 int[] orange = queue.poll();
23                 int r = orange[0];
24                 int c = orange[1];
25                 if (r - 1 >= 0 && grid[r - 1][c] == 1) {
26                     grid[r - 1][c] = 2;
27                     count--;
28                     queue.offer(new int[] { r - 1, c });
29                 }
30                 if (r + 1 < M && grid[r + 1][c] == 1) {
31                     grid[r + 1][c] = 2;
32                     count--;
33                     queue.offer(new int[] { r + 1, c });
34                 }
35                 if (c - 1 >= 0 && grid[r][c - 1] == 1) {
36                     grid[r][c - 1] = 2;
37                     count--;
38                     queue.offer(new int[] { r, c - 1 });
39                 }
40                 if (c + 1 < N && grid[r][c + 1] == 1) {
41                     grid[r][c + 1] = 2;
42                     count--;
43                     queue.offer(new int[] { r, c + 1 });
44                 }
45             }
46         }
47         if (count > 0) {
48             return -1;
49         } else {
50             return round;
51         }
52     }
53 }

Java BFS实现二，个人觉得这种实现对坐标的管理更容易记住

 1 class Solution {
 2     public int orangesRotting(int[][] grid) {
 3         int m = grid.length;
 4         int n = grid[0].length;
 5         Queue<int[]> queue = new LinkedList<>();
 6         int count = 0;
 7         for (int i = 0; i < m; i++) {
 8             for (int j = 0; j < n; j++) {
 9                 if (grid[i][j] == 1) {
10                     count++;
11                 } else if (grid[i][j] == 2) {
12                     queue.offer(new int[] { i, j });
13                 }
14             }
15         }
16 
17         int[][] DIRS = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
18         int round = 0;
19         while (count > 0 && !queue.isEmpty()) {
20             round++;
21             int size = queue.size();
22             for (int i = 0; i < size; i++) {
23                 int[] orange = queue.poll();
24                 int x = orange[0];
25                 int y = orange[1];
26                 for (int[] dir : DIRS) {
27                     int newX = x + dir[0];
28                     int newY = y + dir[1];
29                     // 邻居节点在矩阵内 + 也是个烂橘子
30                     if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1) {
31                         count--;
32                         grid[newX][newY] = 2;
33                         queue.offer(new int[] { newX, newY });
34                     }
35                 }
36             }
37         }
38         if (count > 0) {
39             return -1;
40         }
41         return round;
42     }
43 }

JavaScript实现

 1 /**
 2  * @param {number[][]} grid
 3  * @return {number}
 4  */
 5 var orangesRotting = function (grid) {
 6     let q = [];
 7     let newFresh = 0;
 8     let minutes = 0;
 9     // push rotten oranges to the stack and count fresh oranges
10     for (let i = 0; i < grid.length; i++) {
11         for (let j = 0; j < grid[i].length; j++) {
12             if (grid[i][j] === 2) q.push([i, j]);
13             if (grid[i][j] === 1) newFresh++;
14         }
15     }
16 
17     while (q.length && newFresh) {
18         let newQ = []; // queue for next minute
19         while (q.length) {
20             let badOrange = q.shift();
21             let newRottens = infectOthers(grid, badOrange[0], badOrange[1], newQ);
22             newFresh -= newRottens;
23         }
24         minutes++;
25         q = newQ;
26     }
27     if (newFresh !== 0) return -1;
28     return minutes;
29 };
30 
31 // Infect surrounding oranges
32 // Return the number of newly infected oranges
33 var infectOthers = function (grid, i, j, q) {
34     let infected = 0;
35     if (i > 0 && grid[i - 1][j] === 1) {
36         grid[i - 1][j]++;
37         infected++;
38         q.push([i - 1, j]);
39     }
40     if (j > 0 && grid[i][j - 1] === 1) {
41         grid[i][j - 1]++;
42         infected++;
43         q.push([i, j - 1]);
44     }
45     if (i < grid.length - 1 && grid[i + 1][j] === 1) {
46         grid[i + 1][j]++;
47         infected++;
48         q.push([i + 1, j]);
49     }
50     if (j < grid[0].length - 1 && grid[i][j + 1] === 1) {
51         grid[i][j + 1]++;
52         infected++;
53         q.push([i, j + 1]);
54     }
55     return infected;
56 }

LeetCode 题目总结