leetcode-solutions/1765.py at main · juneguo257/leetcode-solutions · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
from collections import deque

class Solution:
    def handleTile(self, node, q, m, n, retMap):
        i, j, newDepth = node
        if (i >= 0 and i < m):
            if (j >= 0 and j < n):
                if (retMap[i][j] == -1):
                    retMap[i][j] = newDepth
                    self.addNeighborsToQueue(q, i, j, newDepth + 1)

    def addNeighborsToQueue(self, q, i, j, newDepth):
        q.append((i + 1, j, newDepth))
        q.append((i - 1, j, newDepth))
        q.append((i, j - 1, newDepth))
        q.append((i, j + 1, newDepth))

    def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
        m = len(isWater)
        n = len(isWater[0])

        # init the map w/ -1 (denotes height hasn't been init'd yet)
        retMap = [[-1 for _ in range(n)] for _ in range(m)]
        q = deque()

        # fill in water first
        for i in range(m):
            for j in range(n):
                if (isWater[i][j] == 1):
                    retMap[i][j] = 0

        # then get the layers around the water
        for i in range(m):
            for j in range(n):
                if (retMap[i][j] == 0):
                    # fill in land around water
                    if (i - 1 >= 0 and retMap[i - 1][j] == -1): # up
                        retMap[i - 1][j] = 1
                        self.addNeighborsToQueue(q, i - 1, j, 2)
                    if (i + 1 < m and retMap[i + 1][j] == -1): # down
                        retMap[i + 1][j] = 1
                        self.addNeighborsToQueue(q, i + 1, j, 2)
                    if (j - 1 >= 0 and retMap[i][j - 1] == -1): # left
                        retMap[i][j - 1] = 1
                        self.addNeighborsToQueue(q, i, j - 1, 2)
                    if (j + 1 < n and retMap[i][j + 1] == -1): # right
                        retMap[i][j + 1] = 1
                        self.addNeighborsToQueue(q, i, j + 1, 2)

        while (len(q) > 0):
            self.handleTile(q.popleft(), q, m, n, retMap)

        return retMap