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

「LeetCode每日一题」—— 542. 01 矩阵

flypython • • leetcode题解

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

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 14/04/2020 10:51
下一篇 » 16/04/2020 10:55

相关推荐