20240513 994 - Medium - BFS

Problem: 994. 腐烂的橘子

[TOC]

不要把题目想的太难，在没有时间复杂度、写暴力算法前就打退堂鼓。本来以为这个题要涉及图论算法了，没有复习想了会打算看题解。

看了眼题解，发现就是一个多源BFS。

• 先统计新鲜橘子个数 freshCnt、搜集当前烂橘子的下标 rottingIndxes
• 定义变烂的橘子个数 changeCnt，需要的分钟数 res
• 当烂橘子 rottingIndxes 不为空，且变烂的橘子个数 changeCnt 和 freshCnt 一致（避免最后一圈全变烂的橘子再被统计一分钟，也可以不用这个条件，直接赋值 res 为 -1 来允许最后一分钟不操作）
  • 当前分钟数加一 res += 1
  • 用一个 tmp 数组缓存这一分钟变烂的橘子x下标
  • 遍历 rottingIndxes 中的元素，把四周的新鲜橘子变烂，changeCnt +=1 ，把这些变烂的橘子下标加入 tmp
  • 更新 rottingIndxes 为 tmp

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])

        rottingIndxes = []
        freshCnt = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    rottingIndxes.append([i, j])
                if grid[i][j] == 1:
                    freshCnt+=1
        if freshCnt == 0: return 0

        changeCnt = 0
        res = 0
        while len(rottingIndxes) > 0 and changeCnt != freshCnt:
            res += 1
            tmp = []
            while len(rottingIndxes) > 0:
                i, j = rottingIndxes.pop()
                if i > 0 and grid[i-1][j] == 1: 
                    grid[i-1][j] = 2
                    tmp.append([i-1, j])
                if j > 0 and grid[i][j-1] == 1:
                    grid[i][j-1] = 2
                    tmp.append([i, j-1])
                if i < n-1 and grid[i+1][j] == 1:
                    grid[i+1][j] = 2
                    tmp.append([i+1, j])
                if j < m-1 and grid[i][j+1] == 1:
                    grid[i][j+1] = 2
                    tmp.append([i, j+1])
            changeCnt += len(tmp)
            rottingIndxes = tmp
        return res if changeCnt == freshCnt else -1