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

与你一起学算法

关注

发布于: 2021 年 02 月 22 日

上周末的时候参加 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