1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「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