Leetcode994-腐烂的橘子-Python实现

• 题目要求：

• 思路：

  • 保护一个 cur 用来保留以后的烂橘子
  • 遍历一遍给定的数组，如果是烂橘子，把横纵坐标 append 到 cur 数组中
  • 定义一个 time 用来保留工夫
  • 应用 while 循环遍历 cur，当 cur 中还有元素时，持续循环，cur 中寄存的是烂橘子的数组下标，遍历这些烂橘子，遍历每个烂橘子的时候再遍历这个烂橘子的上下左右四个格子，如果有陈腐的橘子，把这个陈腐的橘子变为烂橘子，把这个新的烂橘子 append 到 nex 数组中
  • 遍历完结后，把 nex 数组赋给 cur 数组，把工夫 +1，这时候 cur 中还有元素，所以持续 while 循环
  • 当 cur 中没有元素的时候，遍历 grid 数组，看数组中是否还有陈腐橘子，如果有，返回 -1，如果没有，返回工夫 time
• 外围代码：

cur = []
for i in range(len(grid)):
    for j in range(len(grid[0])):
        if grid[i][j] == 2:
            cur.append((i, j))
# 初始化为 -1，因为 cur 中最初一次遍历的时候保留了数组中最初有好橘子变成烂橘子的那些橘子，这些橘子还有遍历一次，然而曾经不会腐烂其余的橘子了
time = -1
while cur:
    nex = []
    for i, j in cur:
        for x, y in [(0, -1), (-1, 0), (1, 0), (0, 1)]:
            tmp_i = i + x
            tmp_j = j + y
            # 判断一下边界
            if tmp_i >= 0 and tmp_i < len(grid) and tmp_j >= 0 and tmp_j < len(grid[0]):
                if grid[tmp_i][tmp_j] == 1:
                    grid[tmp_i][tmp_j] = 2
                    nex.append((tmp_i,tmp_j))
    time += 1
    cur = nex

for i in grid:
    if 1 in i:
        return -1
return time

• 残缺代码：

  • 有一种 corner case 是如果 grid 只有一个格子，外面如果是一个 0 或是一个 2，那么工夫就是 0

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        if len(grid) == 1 and len(grid[-1]) == 1 and grid[0][0] != 1:
            return 0
        cur = []
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    cur.append((i, j))
        time = -1
        while cur:
            nex = []
            for i, j in cur:
                for x, y in [(0, -1), (-1, 0), (1, 0), (0, 1)]:
                    tmp_i = i + x
                    tmp_j = j + y
                    if tmp_i >= 0 and tmp_i < len(grid) and tmp_j >= 0 and tmp_j < len(grid[0]):
                        if grid[tmp_i][tmp_j] == 1:
                            grid[tmp_i][tmp_j] = 2
                            nex.append((tmp_i,tmp_j))
            time += 1
            cur = nex
        
        for i in grid:
            if 1 in i:
                return -1
        return time