1 題目描述

2 解題思路

我們從水域格子處開始廣搜，也就是從水平面（0的位置）開始向外傳播“水域能量”，直到到達邊界或者多股“水域能量”匯聚（因為廣搜每次只搜索周圍一圈，所以每個水域格子波動的速度/向外傳播的水域能量是一樣的）。那么最后遍歷到的陸地就是傳播范圍最遠的陸地，也就是最高（值最大）的那一個點。

?

這道題不太適用深搜，因為你對每一個水域格子深搜，可以深搜到很遠的格子，此時這個格子的數值很大。但是這個格子可能旁邊就是另一個水域格子，可能理論上值應該很小。那么怎么權衡，是比較繁瑣的。

class Solution:def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:num_l=len(isWater)num_r=len(isWater[0])ret=[[0 for j in range(num_r)] for i in range(num_l)] #最終要返回的矩陣，一開始都在水平基準面上water=[] #存放水域、水域能量到達的點for i in range(num_l):for j in range(num_r):if(isWater[i][j]==1):water.append((i,j))while(water):x,y=water.pop(0)for tmp_x,tmp_y in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:if(0<=tmp_x<num_l and 0<=tmp_y<num_r and isWater[tmp_x][tmp_y]==0):isWater[tmp_x][tmp_y]=1 # 表示水域能量已經到這個點了ret[tmp_x][tmp_y]=ret[x][y]+1 #那么比把能量傳過來的點多1water.append((tmp_x,tmp_y))return(ret)

?

總結

以上是生活随笔為你收集整理的文巾解题 1765. 地图中的最高点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。