「LeetCode每日一题」—— 542. 01 矩阵
542. 01 矩阵
链接:https://leetcode-cn.com/problems/01-matrix/
难度:中等
题目
点击原文链接跳转查看题目
思路
这道题求的就是每个1到0的最短曼哈顿距离,按照这道题的题意,我们需要从一个点出发求最短的距离。
我们很容易就可以想到用BFS。BFS是把周围的一圈搜索完了,再去搜索下一个圈,慢慢扩大搜索,这和我们求最短距离是一样的。
再来看题目,给出了多个1,要找1到0的最短的距离,其实我们可以找每一个0到1的距离,这样就是多个起始点的BFS。
我们的思路就是,多个起始点的BFS,就先遍历一遍矩阵,把所有的0先加入队列。开始遍历,记录当前遍历的层数,把每个还没有搜索到的点依次放入队列,然后再弹出队列的头部元素当做当前遍历点,知道遍历完成。
代码见解决方案。
方案代码
解决方案:
class Solution:
def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
M, N = len(matrix), len(matrix[0])
queue = collections.deque()
visited = [[0] * N for _ in range(M)]
res = [[0] * N for _ in range(M)]
for i in range(M):
for j in range(N):
if matrix[i][j] == 0:
queue.append((i, j))
visited[i][j] = 1
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
step = 0
while queue:
size = len(queue)
for i in range(size):
x, y = queue.popleft()
if matrix[x][y] == 1:
res[x][y] = step
for dx, dy in dirs:
newx, newy = x + dx, y + dy
if newx < 0 or newx >= M or newy < 0 or newy >= N or visited[newx][newy] == 1:
continue
queue.append((newx, newy))
visited[newx][newy] = 1
step += 1
return res
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/329.html
您必须登录才能发表评论。