动态网格问题

这里的动态网格问题，指的是这样一类问题：存在一个网格盘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. 生命游戏也是动态网格问题，可合并练习