每日一道算法题 994. 腐烂的橘子

题目

994. 腐烂的橘子 - 力扣（LeetCode）

Python

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # 分类，挑好坏橘子
        m,n=len(grid),len(grid[0])
        have_good=False
        rot_orange=[]
        for r in range(m):
            for c in range(n):
                if grid[r][c]==2:
                    rot_orange.append((r,c))
                elif grid[r][c]==1:
                    have_good=True
        if not have_good:
            return 0
        if not rot_orange:
            return -1
        minute=-1
        while True:
            # 记录一下，后续需要进行比较
            pre_len=len(rot_orange)
            for _ in range(pre_len):
                x,y=rot_orange[_]
                for dx in (-1,0,1):
                    for dy in (-1,0,1):
                        # 只需要四个方向，上下左右，对角线方向的去掉
                        if dx==0 or dy==0:
                            if m>x+dx>=0 and n>y+dy>=0 and grid[x+dx][y+dy]==1:
                                grid[x+dx][y+dy]=2
                                rot_orange.append((x+dx,y+dy))
            minute+=1
            # 长度没有变化，退出
            if pre_len==len(rot_orange):
                break
        # 判断是否还有好橘子
        for r in range(m):
            for c in range(n):
                if grid[r][c]==1:
                    return -1
        return minute

C++

C语言