LeetCode 两次踩坑后，我终于学会了 BFS

与你一起学算法

发布于 2021-03-23 14:58:00

2840

发布于 2021-03-23 14:58:00

文章被收录于专栏：与你一起学算法

上周末的时候参加 LeetCode 周赛，碰到了一道题。感觉很有意思，而且收获也不小，记录一下。

题目链接如下：

https://leetcode-cn.com/problems/map-of-highest-peak/

题目描述：

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由陆地和水域单元格组成的地图。

如果 isWater[i][j] == 0 ，格子 (i, j)是一个陆地格子。
如果 isWater[i][j] == 1 ，格子 (i, j) 是一个水域格子。

你需要按照如下规则给每个单元格安排高度：

每个格子的高度都必须是非负的。
如果一个格子是是水域，那么它的高度必须为 0 。
任意相邻的格子高度差至多为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）

找到一种安排高度的方案，使得矩阵中的最高高度值最大。

请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

当时时间就剩 20 分钟了，读完题后，也没有啥想法，刚开始就想放弃了。但是感觉又好像在哪见过类似的，好像是之前在 csp 认证的题库上看到的。

又仔细想了想，这就是一个 BFS 嘛， 只不过不同的是这次广度优先进行搜索的时候要从多个源头进行搜索，又称多源 BFS。

仿佛看到了希望，于是我赶紧写代码，Debug，输入测试样例，结果不对，再调试，终于在结束前的一分钟把测试样例给调试对了。

赶紧提交代码，结果等了一会后，运行超时了，真是裂开。。。

当时的提交结果

当时提交的代码如下：

import queue


class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        q = queue.Queue()
        m, n = len(isWater), len(isWater[0])
        res = [[-1 for _ in range(n)] for _ in range(m)]
        dx = [-1, 1, 0, 0]
        dy = [0, 0, 1, -1]
        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:
                    res[i][j] = 0
                    q.put((i, j, res[i][j]))
        while not q.empty():
            row, col, value = q.get()
            for i in range(4):
                fx = row + dx[i]
                fy = col + dy[i]
                if 0 <= fx and fx < m:
                    if 0 <= fy and fy < n:
                        if res[fx][fy] == -1:
                            res[fx][fy] = value + 1
                            q.put((fx, fy, res[fx][fy]))
        return res

没办法，只能去睡觉了。

第二天，我看了下别人写的通过了的代码，发现就优化了一点，那就是设置了一个额外变量，用于记录已经设置了高度的格子个数，这样的话，如果已经设置了高度的格子数目等于了数组的第一维度和第二维度的乘积，这时，即便队列中还有元素，也不再进行搜索了。

简单修改下代码，提交上去，确实通过了。

修改后的代码如下：

import queue


class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        q = queue.Queue()
        m, n = len(isWater), len(isWater[0])
        res = [[-1 for _ in range(n)] for _ in range(m)]
        dx = [-1, 1, 0, 0]
        dy = [0, 0, 1, -1]
        cnt = 0
        for i in range(m):
            for j in range(n):
                if isWater[i][j] == 1:
                    res[i][j] = 0
                    cnt += 1
                    q.put((i, j, res[i][j]))
        while not q.empty():
            row, col, value = q.get()
            for i in range(4):
                fx = row + dx[i]
                fy = col + dy[i]
                if 0 <= fx and fx < m:
                    if 0 <= fy and fy < n:
                        if res[fx][fy] == -1:
                            res[fx][fy] = value + 1
                            cnt += 1
                            if cnt == m*n:
                                return res
                            q.put((fx, fy, res[fx][fy]))
        return res

周赛结束后，我特地去找了之前 csp 认证网站上的类似题目，一找就找到了，题目的链接如下：

http://118.190.20.162/view.page?gpid=T13

感兴趣的可以看下，虽然题目不同，但考察的依然是多源 BFS。

我记得当时这道题就没有完全通过，于是当即又写了一遍，结果还是没有完全通过。

最优配餐

不过我查阅资料发现这个得 70 分不是算法设计的问题，而是跟程序选用的语言有关系，同样的程序，用 C++ 实现就可以通过，但是用 Python 实现就不能完全通过，而且网上也没有查到用 Python 实现完全通过的程序。

总结

之前第一次碰到最优配餐这道题的时候，我记得自己是想到了 BFS，但是没想到从多个源头进行搜索，这一次也想到了多源 BFS，但是优化没有做好。虽然两次都没有把题目做对，不过感觉自己对 BFS 的掌握更加透彻了。

另外，如果有问题的话，可以参考我在 LeetCode 写的题解：

https://leetcode-cn.com/problems/map-of-highest-peak/solution/duo-yuan-bfsxiang-xi-fen-xi-wei-sha-bfs-qo5s8/

也欢迎添加我的微信：yuniXiaomn,一起学习交流。