LC-994. 腐烂的橘子-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

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

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子周围 4 个方向上相邻的新鲜橘子都会腐烂。

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

示例 1:

输入： grid = [[2,1,1],[1,1,0],[0,1,1]]
输出： 4
复制代码

示例 2:

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

示例 3:

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

提示：

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

题解

很明显这道题是通过多源广度优先遍历来进行处理的，因为每次一遍历都是处理与之相邻的上下左右四个方向的位置，且不止一次位置处开始广度优先遍历，所以是多源。

需要提前把格子内所有的橘子拿出来 countAll ，每次将坏的橘子进行 countAll–，最后判断 countAll 是否为空，就得到是否所有橘子都腐烂了。

这里注意

0 的时候，直接腐烂
-1 的时候，就是不可能让所有橘子都腐烂

1.bfs 广度优先遍历

const orangesRotting = (grid) => {
  const returnValue = (x, y) => {
    return grid[x][y]
  }

  const isExistence = (x, y) => {
    if (x >= rowLength || y >= columnLength || x < 0 || y < 0) return false
    return true
  }

  const positionTop = (x, y) => {
    return [x - 1, y]
  }
  const positionBottom = (x, y) => {
    return [x + 1, y]
  }
  const positionLeft = (x, y) => {
    return [x, y - 1]
  }
  const positionRight = (x, y) => {
    return [x, y + 1]
  }

  const getList = () => {
    for (let i = 0; i < rowLength; i++) {
      for (let j = 0; j < columnLength; j++) {
        if (grid[i][j] > 0) {
          countAll += 1
          if (grid[i][j] === 2) {
            badList.push([i, j])
          }
        }
      }
    }
  }

  // 判断是否是正常的橘子 并将正常橘子转化为坏橘子
  const isNormal = (list) => {
    const [x, y] = list
    if (!isExistence(x, y)) return false

    if (returnValue(x, y) === 1) {
      grid[x][y] = 2
      return true
    } else {
      return false
    }
  }

  const breadthFunc = () => {
    // 1~2
    while (badList.length) {
      // 每一轮都会将 badList 里面所有的坏橘子全部清理
      const badListLength = badList.length

      countAll -= badListLength

      // 创建 下一轮 坏的橘子
      const newBadList = new Array()

      console.log(badList)
      badList.forEach((item) => {
        const [x, y] = item

        if (isNormal(positionTop(x, y))) {
          newBadList.push(positionTop(x, y))
        }
        if (isNormal(positionBottom(x, y))) {
          newBadList.push(positionBottom(x, y))
        }
        if (isNormal(positionLeft(x, y))) {
          newBadList.push(positionLeft(x, y))
        }
        if (isNormal(positionRight(x, y))) {
          newBadList.push(positionRight(x, y))
        }
      })
      badList = newBadList
      if (badList.length) nums++
    }
  }

  const rowLength = grid.length
  const columnLength = grid[0].length
  let badList = []
  let countAll = 0 // 存放所有橘子
  let nums = 0 // 执行了多少次

  getList()

  breadthFunc()

  return countAll === 0 ? nums : -1
}
复制代码