难度: Medium
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：mat = [[0,0,0],[0,1,0],[0,0,0]] 输出：[[0,0,0],[0,1,0],[0,0,0]]
示例 2：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]] 输出：[[0,0,0],[0,1,0],[1,2,1]]
提示：
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j] is either 0 or 1.mat 中至少有一个 0 注意：本题与主站 542 题相同：https://leetcode-cn.com/problems/01-matrix/
运行时间: 104 ms
内存: 20.3 MB
class Solution:
def updateMatrix(self, mat):
m = len(mat)
n = len(mat[0])
res = [[-1]*n for _ in range(m)]
travel = [[False]*n for _ in range(m)]
stack = []
for i in range(m):
for j in range(n):
if mat[i][j]==0:
res[i][j] = 0
travel[i][j] = True
stack.append((i,j))
stage = 0
while stack:
tmp = []
for i,j in stack:
res[i][j] = stage
if i>0 and travel[i-1][j]==False:
tmp.append((i-1,j))
travel[i-1][j] = True
if i<m-1 and travel[i+1][j]==False:
tmp.append((i+1,j))
travel[i+1][j] = True
if j>0 and travel[i][j-1]==False:
tmp.append((i,j-1))
travel[i][j-1] = True
if j<n-1 and travel[i][j+1]==False:
tmp.append((i,j+1))
travel[i][j+1] = True
stage+=1
stack = tmp
return res
本题解采用广度优先搜索（BFS）来找出矩阵中每个元素到最近的0的距离。首先，将所有值为0的元素的位置加入到队列中，并初始化它们的距离为0。对于矩阵中的1，距离初始化为-1表示未访问。队列中的元素依次出队，对其四个方向的邻居进行检查。如果邻居未被访问过（即距离为-1），则更新其距离为当前元素的距离加1，并将其加入队列中继续处理。这一过程重复进行，直到队列为空。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def updateMatrix(self, mat):
m = len(mat)
n = len(mat[0])
res = [[-1]*n for _ in range(m)] # 结果矩阵初始化为-1
travel = [[False]*n for _ in range(m)] # 访问记录矩阵
stack = []
for i in range(m):
for j in range(n):
if mat[i][j]==0:
res[i][j] = 0 # 初始化0的位置距离为0
travel[i][j] = True # 标记为已访问
stack.append((i,j)) # 将0的位置加入队列
stage = 0
while stack:
tmp = []
for i,j in stack:
res[i][j] = stage # 更新距离
# 检查四个方向的邻居
if i>0 and travel[i-1][j]==False:
tmp.append((i-1,j))
travel[i-1][j] = True
if i<m-1 and travel[i+1][j]==False:
tmp.append((i+1,j))
travel[i+1][j] = True
if j>0 and travel[i][j-1]==False:
tmp.append((i,j-1))
travel[i][j-1] = True
if j<n-1 and travel[i][j+1]==False:
tmp.append((i,j+1))
travel[i][j+1] = True
stage+=1 # 增加BFS的层次
stack = tmp # 更新队列
return res
在初始化距离矩阵时选择-1作为未访问的标识是因为-1在此上下文中是一个明显的非法值，因为距离不可能为负数。使用-1可以立即区分出哪些元素尚未被访问或更新，这样做可以避免使用额外的数据结构来跟踪访问状态，从而节省内存和简化代码逻辑。如果使用其他数值，如正整数，可能会与有效的距离值混淆，使得算法的判断更加复杂。
在广度优先搜索（BFS）中，通过一个访问记录矩阵 'travel' 来确保每个点只被访问一次。一旦一个点被访问，即将它的访问状态标记为 'True'。在后续的搜索过程中，只有未被访问（即其状态为 'False'）的点才会被加入到队列中。这样确保了每个点仅在首次达到时被处理一次，避免了重复计算和不必要的资源浪费。
在BFS中，使用队列是为了保证先进入队列的节点先被处理，从而按层次（从近到远）处理每个节点。这种层次化处理确保了距离的正确计算，并且能够较快地到达所有节点。而使用栈实现深度优先搜索(DFS)会导致算法先深入到可能的最远点，这样做在寻找最短路径问题中效率较低，因为它可能走很多不必要的路径。此外，DFS在处理大数据量时可能会因递归过深而导致栈溢出，而BFS则通常不会遇到这样的问题。