题目

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

  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。

每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  1. 1 <= grid.length <= 10
  2. 1 <= grid[0].length <= 10
  3. grid[i][j] 仅为 0、1 或 2

难度

★☆☆☆

解答思路

  1. 遍历出所有坏橘子2，存下来。
  2. 隔一分钟用坏橘子感染周边新鲜橘子。
  3. 对比一下和上次的图是否一样
    • 如果一样，说明无法再感染，算出新鲜橘子的数量，如果没有新鲜橘子了，说明全部感染，返回分钟数。如果有，说明不可能做到，返回-1。
    • 如果不一样，继续感染

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
 * @param {number[][]} grid
 * @return {number}
 */
const orangesRotting = function(grid) {
  // 保存上一次的图形
  let lastGridString = grid.toString()

  if (lastGridString.indexOf(1) === -1) {
    return 0
  }

  let count = 0
  const xLen = grid.length
  const yLen = grid[0].length

  // 找出坏橘子存下来
  let laterRottedOranges = []
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j] === 2) {
        laterRottedOranges.push([i, j])
      }
    }
  }

  while (true) {
    const tempRottedOranges = laterRottedOranges.slice(0)
    // 存储新的被感染的坏橘子
    laterRottedOranges = []
    for (let i = 0; i < tempRottedOranges.length; i++) {
      let x = tempRottedOranges[i][0]
      let y = tempRottedOranges[i][1]
      if (x > 0 && grid[x - 1][y] === 1) {
        laterRottedOranges.push([x - 1, y])
        grid[x - 1][y] = 2
      }
      if (x < xLen - 1 && grid[x + 1][y] === 1) {
        laterRottedOranges.push([x + 1, y])
        grid[x + 1][y] = 2
      }
      if (y > 0 && grid[x][y - 1] === 1) {
        laterRottedOranges.push([x, y - 1])
        grid[x][y - 1] = 2
      }
      if (y < yLen - 1 && grid[x][y + 1] === 1) {
        laterRottedOranges.push([x, y + 1])
        grid[x][y + 1] = 2
      }
    }
    // 比较是否相等
    const gridString = grid.toString()
    if (gridString !== lastGridString) {
      count++
      lastGridString = gridString
    } else {
      break
    }
  }
  // 看还有没有=1的
  if (lastGridString.indexOf(1) > -1) {
    return -1
  }

  return count
}