这个题目的想法是从martrix 中的0开始，向周边开始+1，如果result里面的值已经小于“这次扩张”的值，就不更新里面的值，这说明有一个0，离这个格子比较近。
只有这个格子的值被刷新了，我们才把它放入队列中，让BFS继续。原因是如果它被刷新了，那么它的周边也可能需要刷新。
BFS总是使用一个队列。也许是因为队列这个数据结构比较主观，不需要采用更加难理解的递归。
import math from collections import deque class Solution: def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]: result = [ [math.inf]*len(matrix[0]) for _ in range(len(matrix))] q = deque() for row in range(len(matrix)): for col in range(len(matrix[0])): if matrix[row][col] == 0: q.append((row, col)) result[row][col] = 0 while q: row, col = q.popleft() # explore all 4 directions direction = [[-1,0], [1,0], [0,-1], [0,1]] for i in range(4): new_row = direction[i][0] + row new_col = direction[i][1] + col if new_row >=0 and new_col >=0 and new_row < len(matrix) and new_col < len(matrix[0]): if result[new_row][new_col] > result[row][col] + 1: result[new_row][new_col] = result[row][col] + 1 q.append((new_row, new_col)) return result还有DP的方法。先把0的位置result设成0. 从左到右和从上到下扫描，比较两个neighbor+1，和当前的result。 然后，反过来从右到左，和从下到上扫描一遍。 为什么两遍扫描就可以了呢？因为最小距离是四个邻居的最小值+1 第一遍扫了两个邻居。第二遍又扫了两个邻居。
import math from collections import deque class Solution: def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]: rows = len(matrix) if rows==0: return matrix cols = len(matrix[0]) dist = [[math.inf for _ in range(cols)] for _ in range(rows)] for i in range(0, rows): for j in range(0, cols): if matrix[i][j] == 0: dist[i][j] = 0 else: if i>0: dist[i][j] = min(dist[i][j], dist[i-1][j] + 1) if j>0: dist[i][j] = min(dist[i][j], dist[i][j-1] + 1) for i in range(rows-1, -1, -1): for j in range(cols-1, -1, -1): if i<rows-1: dist[i][j] = min(dist[i][j], dist[i+1][j]+1) if j<cols-1: dist[i][j] = min(dist[i][j], dist[i][j+1]+1) return dist