上周末的时候参加 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
。找到一种安排高度的方案,使得矩阵中的最高高度值 最大 。
请你返回一个大小为 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,一起学习交流。
推荐阅读: