aboutsummaryrefslogtreecommitdiff
path: root/map_highest_peak.py
blob: 78bae7dd512fe2370d07212e3cda30222668b312 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 1765. Map of Highest Peak
from collections import deque

"""
you are given an integer matrix 'isWater' of size 'm x n' that represents a
map of land and water cells. if 'isWater[i][j] == 0' cell '(i, j)' is a land
cell. if 'isWater[i][j] == 1', cell '(i, j)' is a water cell. you must assign
each cell a height in a way that follows the given rules. find an assignment
of heights such that the maximum height in the matrix is maximised.
"""


class Solution(object):
    def highestPeak(self, isWater):
        """
        :type isWater: List[List[int]]
        :rtype: List[List[int]]
        """
        m, n = len(isWater), len(isWater[0])
        height = [[-1] * n for _ in range(m)]
        bfs = deque([])
        for r in range(m):
            for c in range(n):
                if isWater[r][c] == 1:
                    bfs.append((r, c))
                    height[r][c] = 0
        dir = [0, 1, 0, -1, 0]
        while bfs:
            r, c = bfs.popleft()
            for i in range(4):
                nr, nc = r + dir[i], c + dir[i + 1]
                if nr < 0 or nr == m or nc < 0 or nc == n or height[nr][nc] != -1:
                    continue
                height[nr][nc] = height[r][c] + 1
                bfs.append((nr, nc))
        return height


if __name__ == "__main__":
    obj = Solution()
    print(obj.highestPeak(isWater=[[0, 1], [0, 0]]))
    print(obj.highestPeak(isWater=[[0, 0, 1], [1, 0, 0], [0, 0, 0]]))