LC 0778 [H] Swim in Rising Water - ALawliet/algorithms GitHub Wiki
Dijkstra's is just BFS with a min heap, but instead of finding the shortest path, we want to find the path with min height/time
time is max height to get to the end
Translation:
From top left to right bottom, there are many paths. For each path we have one maximum value. Let's find the minimal one of such maximum value.
So the minimal maximum value in each path.
The exactly same question is 1102
What is the earliest time t when coordinate (0,0) and (n-1,n-1) are connected?
Two adjacent coordinates are connected if and only if their values are both less than or equal to t.
We are looking for the smallest possible t.
T: O(n^2logn) average
from queue import PriorityQueue
DIRS = ([0,1],[0,-1],[1,0],[-1,0])
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
N = len(grid)
minH = PriorityQueue()
minH.put( [grid[0][0], 0, 0] ) # (time/max-height, r, c)
visited = set()
visited.add( (0, 0) )
while minH:
t, r, c = minH.get()
visited.add( (r, c) )
if r == N-1 and c == N-1:
return t
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N and (nr, nc) not in visited:
minH.put( [max(t, grid[nr][nc]), nr, nc] )
visited.add( (nr, nc) )