aboutsummaryrefslogtreecommitdiff
path: root/map_highest_peak.py
diff options
context:
space:
mode:
Diffstat (limited to 'map_highest_peak.py')
-rw-r--r--map_highest_peak.py42
1 files changed, 42 insertions, 0 deletions
diff --git a/map_highest_peak.py b/map_highest_peak.py
new file mode 100644
index 0000000..78bae7d
--- /dev/null
+++ b/map_highest_peak.py
@@ -0,0 +1,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]]))