aboutsummaryrefslogtreecommitdiff
path: root/swim_rising_water.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-10-05 21:25:03 -0600
committerJack Sangdahl <[email protected]>2025-10-05 21:25:03 -0600
commit074c3349009c013f98f1dff329270f1eee1f2db8 (patch)
tree6c85ba20dcb7a0ce0e5aa74e663ff3b64988881b /swim_rising_water.py
parentb655133617e644bd958c4b3356c04ad7a92718f1 (diff)
downloadleetcode-074c3349009c013f98f1dff329270f1eee1f2db8.tar.gz
leetcode-074c3349009c013f98f1dff329270f1eee1f2db8.zip
778. swim in rising water
Diffstat (limited to 'swim_rising_water.py')
-rw-r--r--swim_rising_water.py55
1 files changed, 55 insertions, 0 deletions
diff --git a/swim_rising_water.py b/swim_rising_water.py
new file mode 100644
index 0000000..f161a4c
--- /dev/null
+++ b/swim_rising_water.py
@@ -0,0 +1,55 @@
+# 778. Swim in Rising Water
+import heapq
+
+"""
+you are given an 'n x n' integer matrix 'grid' where each value 'grid[i][j]'
+represnts the elevation at that point '(i, j)'. it starts raining and water
+gradually rises over time. at time 't', the water level is 't', meaning any
+cell with elevation less than or equal to 't' is submerged or reachable. you
+can swim from a square to another 4-direction adjacent square if and only if
+the elevation of both squares individually are at most 't'. you can swim
+infinite distances in zero time. of course, you must stay within the
+boundaries of the grid. return the minimum time until you can reach the
+bottom right . you can swim infinite distances in zero time. of course, you
+must stay within the boundaries of the grid. return the minimum time until
+you can reach the bottom right square if you start at the top left. you can
+swim infinite distances in zero time. of course, you must stay within the
+boundaries of the grid. return the minimum time until you can reach the
+bottom right square if you start at the top left..square if you start at the
+top left.
+"""
+
+
+class Solution(object):
+ def swimInWater(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ n, ans = len(grid), 0
+ pq = [(grid[0][0], 0, 0)]
+ vis = set([(0, 0)])
+ while True:
+ tmp, x, y = heapq.heappop(pq)
+ if x == y == n - 1:
+ return ans
+ for i, j in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
+ if 0 <= i < n and 0 <= j < n and (i, j) not in vis:
+ vis.add((i, j))
+ heapq.heappush(pq, (grid[i][j], i, j))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.swimInWater(grid=[[0, 2], [1, 3]]))
+ print(
+ obj.swimInWater(
+ grid=[
+ [0, 1, 2, 3, 4],
+ [24, 23, 22, 21, 5],
+ [12, 13, 14, 15, 16],
+ [11, 17, 18, 19, 20],
+ [10, 9, 8, 7, 6],
+ ]
+ )
+ )