动态网格问题
这里的动态网格问题，指的是这样一类问题：存在一个网格盘grid，其中的各个网格存放着对应的值，并且这些值会按照某些规则变化，从而使整个grid的内容逐轮发生改变
动态网格问题的暴力通解
一般而言，动态网格问题中，所有网格内的值必须按照规则【同时】由前一状态改变至后一状态。问题就出在这里，要求同时，但在程序中计算各个网格的值改变过程肯定有先后顺序，先计算出来的网格结果不能影响后续网格的值的计算。那么，对于已经计算出来的结果，我们就不能直接在grid上原地修改，需要另外开辟一块与grid等大的空间temp_grid来存放得到的结果，而grid则保持原样，遍历完grid的所有网格后，temp_grid就是grid下一次的状态
总结一句话，动态网格问题最大的特点就是【同时改变】，可以借用额外空间temp_grid实现
获取邻居的代码模板：
# 使用yield生成器获取坐标(r, c)上下左右相邻的有效位置，R为总行数，C为总列数
def getNeighbors(r, c):
for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
下面2个是比较典型的动态网格问题
例
例1
【病毒感染】
给定一个 m * n 的grid，其中的每个网格要么住病人，要么住正常人，要么无人居住，分别以2/1/0表示
感染规则：每个病人每分钟可以感染其上下左右的4个相邻网格
求：若最终网格内的人全部被感染，给出需要的最短时间；若网格内的人无法全部被感染，返回-1
原题为leetcode994 腐烂的橘子https://leetcode-cn.com/problems/rotting-oranges/
不管三七二十一，先来个暴力通解
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
R = len(grid)
C = len(grid[0])
# 定义查找邻居的方法
def neighbors(r, c):
for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
count_minute = 0
# 【核心代码，但不难，就是单纯翻译规则而已】开始扫描grid，并将值写入temp_grid
while True:
# 开辟temp_grid存放grid变化到下一次的状态
temp_grid = [[0 for j in range(C)] for i in range(R)]
new_infected_flag = 0
alive_flag = 0
for i in range(R):
for j in range(C):
# 把所有感染的位置标记在temp_grid
if grid[i][j] == 2:
temp_grid[i][j] == 2
# 检查邻居
for nr, nc in neighbors(i, j):
if grid[nr][nc] == 1:
new_infected_flag = 1
temp_grid[nr][nc] = 2
# 补全剩余的temp_grid网格
for i in range(R):
for j in range(C):
if temp_grid[i][j] == 0:
temp_grid[i][j] = grid[i][j]
# 如果存活，则标记一下
if temp_grid[i][j] == 1:
alive_flag = 1
# 如果没有新的感染
if not new_infected_flag:
break
count_minute += 1
grid = temp_grid
if alive_flag:
return -1
return count_minute
暴力可以解决，现在看一看更美丽的解法
进一步分析：
这是一个一次性动态网格问题，因为任何格子的状态从始至终最多只改变一次。对于每个格子，一旦被感染，就永远处于感染状态不会改变。那么在每一轮扫描时，一旦发现新感染的格子可以马上原地在grid修改为2，如果后续扫描碰到这些新感染的格子时，则跳过。代码可优化如下：
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
R = len(grid)
C = len(grid[0])
# 定义查找邻居的方法
def neighbors(r, c):
for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
count_minute = 0
# 开始扫描grid，并将值写入temp_grid
while True:
new_infected = list()
alive_flag = 0
for i in range(R):
for j in range(C):
# 如果当前格子不是新感染的格子
if [i, j] not in new_infected:
if grid[i][j] == 2:
# 检查邻居
for nr, nc in neighbors(i, j):
if grid[nr][nc] == 1:
new_infected.append([nr, nc])
grid[nr][nc] = 2
elif grid[i][j] == 1:
alive_flag = 1
# 如果没有新的感染
if not new_infected:
break
count_minute += 1
if alive_flag:
return -1
return count_minute
再进一步分析：
上面的做法其实每一次扫描都把古老的病例格扫描了一次，但对于一个病例格，它在完成一次传播（传播到相邻的上下左右位置）后，就“失去了进一步的传染力”，后续再多轮扫描这个病例格只是在做重复的无用功，因为它本身及周围的状态已经确定
我们想的是，每次只关注最近一轮感染的病例格会产生哪些新感染，这背后实际上就是BFS广度优先搜索
广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点，如果同一层都访问完了，再访问下一层。广度优先搜索基于队列实现，每轮将父层的节点出队的同时将子层的节点入队，例如二叉树的层次遍历
感染与被感染等价存在父子关系
直接贴leetcode的题解：
class Solution(object):
def orangesRotting(self, grid):
R, C = len(grid), len(grid[0])
# queue - all starting cells with rotting oranges
queue = collections.deque()
for r, row in enumerate(grid):
for c, val in enumerate(row):
# 将初始时的病例格入队
if val == 2:
queue.append((r, c, 0))
def neighbors(r, c):
for nr, nc in ((r-1,c),(r,c-1),(r+1,c),(r,c+1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, nc
d = 0
# 当队列不为空时，不断将队中的病例格出队，并将被该格感染的子病例格入队
while queue:
r, c, d = queue.popleft()
for nr, nc in neighbors(r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = 2
queue.append((nr, nc, d+1))
if any(1 in row for row in grid):
return -1
return d
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/rotting-oranges/solution/fu-lan-de-ju-zi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
另外，leetcode 289. 生命游戏也是动态网格问题，可合并练习
网友评论