LeetCode-994.腐烂的橘子 - sheep44044的小站

图论#

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

值 0 代表空单元格；

值 1 代表新鲜橘子；

值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

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

示例 1：

1
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
2
输出：4

示例 2：

1
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
2
输出：-1
3
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：

1
输入：grid = [[0,2]]
2
输出：0
3
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

BFS的解法

思路：

容易被题目示例误导的一点是：这里的烂橘子是可以不止一个的，这就与 200. 岛屿数量 有所不同，从“单源”改为“多源”，所以需要先遍历一次网格，把所有初始状态就是 2 的烂橘子全部塞进初始队列中。它们处于同一“层”，地位平等，会像水波纹一样同时向外扩散。
就是rottedThisMinute = true的作用，我们会疑惑时间不是一直在增加的吗，为什么需要这个？

这是因为会遇到像示例3的状况，它们被从 queue 中取出来，此时，它们周围已经没有任何新鲜橘子了（或者被墙挡住了），但程序还会检查，所以这段时间是不需要或者说是没意义的。

1
func orangesRotting(grid [][]int) int {
2
    if len(grid) == 0 {
3
        return 0
4
    }
5

6
    m, n := len(grid), len(grid[0])
7

8
    queue := [][]int{}
9
    fresh := 0
10
    for i := 0; i < m; i++ {
11
        for j := 0; j < n; j++ {
12
            if grid[i][j] == 2 {
13
                queue = append(queue, []int{i, j})
14
            }
15
            if grid[i][j] == 1 {
16
                fresh++
17
            }
18
        }
19
    }
20

21
    if fresh == 0 {
22
        return 0
23
    }
24

25
    time := 0
26
    dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
27
    for len(queue) != 0 {
28
        size := len(queue)
29
        rottedThisMinute := false
30
        for i := 0; i < size; i++ {
31
            cur := queue[0]
32
            queue = queue[1:]
33
            row, col := cur[0], cur[1]
34

35
            for _, v := range dirs {
36
                nr, nc := v[0]+row, v[1]+col
37
                if nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1 {
38
                    grid[nr][nc] = 2
39
                    queue = append(queue, []int{nr, nc})
40
                    fresh--
41
                    rottedThisMinute = true
42
                }
43
            }
44
        }
45

46
        if rottedThisMinute == true {
47
            time++
48
        }
49
    }
50

51
    if fresh != 0 {
52
        return -1
53
    }
54

55
    return time
56
}