题目搬运者
https://leetcode-cn.com/problems/01-matrix/
给定一个mxn的二进制矩阵,返回每个单元格最接近0的距离。
两个相邻单元格之间的距离为1。
思路 广度优先算法
- 从矩阵中是0的位置开始遍历周围一圈
- 将上一步的坐标加入队列,继续遍历周围一圈,有点类似”泛洪“操作
- 为了实验以上两点,需要一个队列将矩阵中是0的位置的坐标加入队列,还需要一个visit访问数组,对于被访问过的数组就不在进行操作。
- 因为改方法是从0开始泛洪,即周围的距离就会使最小的,不需要进行min比较最小距离。
广度优先
class Solution(object):
def updateMatrix(self, mat):
"""
:type mat: List[List[int]]
:rtype: List[List[int]]
"""
n = len(mat) # x
m = len(mat[0]) # y
que = collections.deque()
visit = [[0] * m for _ in range(n)]
dist = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
if mat[i][j] == 0:
que.append([i, j])
visit[i][j] = 1 # 该位置被入队
# bfs
while que:
x, y = que.popleft()
for mx, my in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and visit[mx][my] == 0:
dist[mx][my] = dist[x][y] + 1
que.append((mx, my))
visit[mx][my] = 1
return dist