title
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1：
输入：
[[0,0,0],
[0,1,0],
[0,0,0]]
输出：
[[0,0,0],
[0,1,0],
[0,0,0]]
示例 2：
输入：
[[0,0,0],
[0,1,0],
[1,1,1]]
输出：
[[0,0,0],
[0,1,0],
[1,2,1]]
提示：
- 给定矩阵的元素个数不超过 10000。
- 给定矩阵中至少有一个元素是 0。
- 矩阵中的元素只在四个方向上相邻: 上、下、左、右。
solution
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
if not matrix:
return []
m, n = len(matrix), len(matrix[0])
res = [[-1 for _ in range(n)] for _ in range(m)]
q = collections.deque()
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
q.append((i, j))
res[i][j] = 0
step = 0
dirs = (-1, 0, 1, 0, -1)
while len(q) > 0:
step += 1
for _ in range(len(q)):
ro, co = q.popleft()
for k in range(4):
r, c = ro + dirs[k], co + dirs[k + 1]
if 0 <= r < m and 0 <= c < n and res[r][c] == -1:
res[r][c] = step
q.append((r, c))
return res