题目描述：

在给定的网格中，每个单元格可以有以下三个值之一：
0： 代表空单元格；
1： 代表新鲜橘子；
2： 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
示例 1：
994：腐烂的橘子——广度优先算法 - 图1
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotting-oranges

解题思路：

传统广度优先算法——队列：

  1. class Solution2(object):
  2.     '''标准答案'''
  3.     def orangesRotting(self, grid):
  4.         '''队列多元广度优先收索'''
  5.         R = len(grid) #row 列，横排
  6.         C = len(grid[0]) #column 栏，纵列
  8.         # queue - all starting cells with rotting oranges
  9.         queue = collections.deque()
  10.         #两层循环取得矩阵中的单个元素
  11.         for r,row in enumerate(grid):
  12.             for c,val in enumerate(row):
  13.                 #如果腐烂就入队
  14.                 if val==2:
  15.                     queue.append((r,c,0))
  16.         #写一个能够把上下左右都找出来的生成器,类似enumerate
  17.         #yield 功能和return类似，可以想象为一个一个出
  18.         def neighbors(r,c):
  19.             for nr,nc in ((r-1,c),(r+1,c),(r,c+1),(r,c-1)):
  20.                 if 0 <= nr < R and 0 <= nc < C:
  21.                     yield nr, nc
  23.         d = 0 #d用来记录层级（时间）
  24.         while queue:
  25.             r,c,d =queue.popleft()
  26.             for nr,nc in neighbors(r,c):
  27.                 if grid[nr][nc] ==1:
  28.                     grid[nr][nc]=2
  29.                     queue.append((nr,nc,d+1))
  30.         #循环之后，只要有任何一个橘子没有腐烂，就返回-1
  31.         if any(1 in row for row in grid):
  32.             return -1
  33.         return d

特殊广度优先算法——集合：

  1. class Solution1(object):
  2.     def orangesRotting(self, grid):
  3.         '''集合版广度优先'''
  4.         '''集合（set）是一个无序的不重复元素序列。
  5.         可以使用大括号 { } 或者 set() 函数创建集合
  6.         注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典。'''
  7.         row = len(grid)
  8.         col = len(grid[0])
  10.         #创建集合
  11.         rotten = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 2} # 腐烂集合
  12.         fresh = {(i, j) for i in range(row) for j in range(col) if grid[i][j] == 1}  # 新鲜集合
  13.         time = 0 #时间初始化
  14.         #只要还存在信限橘子就进入循环
  15.         while fresh:
  16.             #如果所有腐烂橘子都已经出集合了，就结束
  17.             if not rotten: return -1
  18.             rotten = {(i + di, j + dj) for i, j in rotten for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)] if (i + di, j + dj) in fresh} # 即将腐烂的如果在新鲜的集合中，就将它腐烂
  19.             fresh -= rotten # 剔除腐烂的
  20.             time += 1
  21.         return time

反思tips

  • 关于python中yield 功能：所谓的函数生成器，和return类似，都是返回一个值。但是yield只会返回一个元素，可以想象为一个一个出，类似enumerate

  • 传统的队列实现其实不一定要使用yield，以下代码可以实现同样的功能

    1. directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    2. for di, dj in directions:
    3.               if 0 <= i + di < row and 0 <= j + dj < col and grid[i + di][j + dj] == 1:
    4.                   grid[i + di][j + dj] = 2
    5.                   queue.append((i + di, j + dj, time + 1))

  • 关于python的集合：集合（set）是一个无序的不重复元素序列。可以使用大括号 { } 或者 set() 函数创建集合注意：创建一个空集合必须用 set() 而不是 { }，因为 { } 是用来创建一个空字典

  • 最后，通过这道题，熟悉row和column这两个变量来描述矩阵。row是横排，col是纵列。