title
problem link On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).
Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually areat mostt. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.
You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?
Example 1:
Input: [[0,2],[1,3]] Output: 3 Explanation: At time 0, you are in grid location (0, 0). You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.
You cannot reach point (1, 1) until time 3. When the depth of water is 3, we can swim anywhere inside the grid.
Example 2:
Input: [[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]] Output: 16 Explanation: 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
The final route is marked in bold. We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
Note:
2 .
grid[i][j] is a permutation of [0, ..., N*N - 1].
在一个 N x N 的坐标方格 grid 中，每一个方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
现在开始下雨了。当时间为 t时，此时雨水导致水池中任意位置的水位为 t。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。
你从坐标方格的左上平台 (0，0) 出发。最少耗时多久你才能到达坐标方格的右下平台
solution
dijkstra and bfs
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
res = 0
import heapq
from collections import defaultdict
visit = defaultdict(bool)
m, n = len(grid), len(grid[0])
N = m * n
pq = []
pq.append((0, 0, 0))
visit[(0,0)] = True
dir = [-1, 0, 1, 0, -1]
while len(pq) > 0:
u = heapq.heappop(pq)
x, y = u[1], u[2]
res = max(res, grid[x][y])
if x == m - 1 and y == n - 1:
return res
for k in range(4):
if (0 <= x + dir[k] < m and 0 <= y + dir[k + 1] < n) and not visit[(x + dir[k], y + dir[k + 1])]:
visit[(x + dir[k], y + dir[k + 1])] = True
heapq.heappush(pq, (grid[x + dir[k]][y + dir[k + 1]], x + dir[k], y + dir[k + 1]))
return res
binary-search
import collections
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
high = max([max(l) for l in grid])
left = 0
m = len(grid)
n = len(grid[0])
def isConnect(t):
dir = [-1, 0, 1, 0, -1]
visit = collections.defaultdict(bool)
def dfs(s):
if not (0 <= s[0] <= m - 1) or not (0 <= s[1] <= n - 1):
return False
if visit[s]:
return False
visit[s] = True
if grid[s[0]][s[1]] > t:
return False
if s == (m - 1, n - 1):
return True
for i in range(4):
x, y = s[0] + dir[i], s[1] + dir[i+1]
if dfs((x, y)):
return True
return False
return dfs((0, 0))
while left < high:
mid = left + (high - left) // 2
if isConnect(mid):
high = mid
else:
left = mid + 1
return high