今日题目

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

思路

由于相邻格子之间高度差的绝对值最大为 1，且水域格子的高度为 0。 因此答案就是每个格子到最近水域格子的曼哈顿距离。

方法

使用 BFS 求每个格子到最近水域格子的曼哈顿距离。

复杂度

  • 时间复杂度：$O(NM)$，N、M 分别为网格的行数和列数。

  • 空间复杂度：$O(NM)$

代码

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        q = deque()
        ans = [[2005 for _ in range(len(isWater[0]))] for _ in range(len(isWater))]
        for i in range(len(isWater)):
            for j in range(len(isWater[0])):
                if isWater[i][j] == 1:
                    q.append((i,j))
                    ans[i][j] = 0
        
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]

        while q:
            x,y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or ny < 0 or nx >= len(isWater) or ny >= len(isWater[0]) or ans[nx][ny] <= ans[x][y] + 1:
                    continue
                ans[nx][ny] = ans[x][y] + 1
                q.append((nx, ny))
        
        return ans