One question per day 1765 The highest point in the map

topic ： Find the height of the highest point that may exist on a two-dimensional map . That is, give the water area on the map , Find a way to fill the blank area with land .

Input m*n Two dimensional array of isWater, Indicates whether the location is a water area .1 yes 0 no .

When calculating height , The height of the water area is 0. And the height difference between adjacent lands is at most 1.

Explain ：

Refer to the explanation of the question . breadth-first BFS, Start from the water , Fill adjacent and unset grids .

class Solution:
    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m, n = len(isWater), len(isWater[0])
        ans = [[water-1 for water in row] for row in isWater] # initialization , Set the water height to 0. Land initialization -1
        q = deque((i,j) for i, row in enumerate(isWater) for j,water in enumerate(row) if water)# Join the team 
        while q:
            i, j = q.popleft()
            for x,y in ((i-1,j),(i+1, j), (i, j-1), (i, j+1)):
                if 0<=x<m and 0<=y<n and ans[x][y] == -1:
                    ans[x][y] = ans[i][j] +1
                    q.append((x,y))
        return ans

Add ：

1.Python The comparison operation in can be concatenated arbitrarily ; for example ,x < y <= z  Equivalent to  x < y and y <= z.

 2.deque The bidirectional queue , Adding or popping elements can be bidirectional .

collections --- Container data type — Python 3.10.2 file


 

 append(), pop() From the right end .

appendleft(), popleft() It's from the left .