难度: Hard
原题连接
内容描述
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 are at most t. 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 <= N <= 50.
grid[i][j] is a permutation of [0, ..., N*N - 1].
思路 1 - 时间复杂度: O(N^2lgN)- 空间复杂度: O(N^2)******
首先要看到一句话：grid[i][j] is a permutation of [0, ..., N*N - 1]， 这句话很重要
priority queue, beats 70.37%
class Solution:
def swimInWater(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
heap, seen, res = [(grid[0][0], 0, 0)], set([(0, 0)]), 0
while True:
T, i, j = heapq.heappop(heap)
res = max(res, T)
if i == j == len(grid) - 1:
return res
for x, y in [(i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)]:
if 0 <= x < len(grid) and 0 <= y < len(grid) and (x, y) not in seen:
seen.add((x, y))
heapq.heappush(heap, (grid[x][y], x, y))思路 2 - 时间复杂度: O(N^3)- 空间复杂度: O(N^2)******
union-find, 每隔一秒，我们就可以到达当前最大高度的那个点（即高度为time的那个点），然后从这个点继续往外走，如果旁边的点的高度小于等于time的话就可以走
每走一步time就加一秒，什么时候0和N^2-1相连了，就说明从(0,0)可以走到(N-1, N-1)了，此时返回time, beats 36.11%
class UnionFind(object):
def __init__(self, n): # 初始化uf数组和组数目
self.count = n
self.uf = [i for i in range(n)]
self.size = [1] * n # 每个联通分量的size
def find(self, x): # 判断节点所属于的组
while x != self.uf[x]:
self.uf[x] = self.uf[self.uf[x]]
x = self.uf[x]
return self.uf[x]
def union(self, x, y): # 连接两个节点
x_root = self.find(x)
y_root = self.find(y)
if x_root == y_root:
return
if self.size[x_root] < self.size[y_root]:
x_root, y_root = y_root, x_root
self.uf[y_root] = x_root
self.size[x_root] += self.size[y_root]
self.size[y_root] = 0
self.count -= 1
def connected(self, x, y): # 判断两个节点是否联通
return self.find(x) == self.find(y)
class Solution:
def swimInWater(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
N = len(grid)
location = {grid[i][j]: (i, j) for i in range(N) for j in range(N)}
uf = UnionFind(N**2)
for time in range(N**2):
i, j = location[time]
for x, y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
new_i, new_j = i + x, j + y
if 0 <= new_i < N and 0 <= new_j < N and grid[new_i][new_j] <= time:
uf.union(i * N + j, new_i * N + new_j)
if uf.connected(0, N**2-1):
return time思路 3 - 时间复杂度: O(N^2lgN)- 空间复杂度: O(N^2)******
二分 + DFS
最多时间为N^2-1, 最少为0，我先看看mid能不能到，不能就继续二分，每一次看能不能到都是一个新的dfs（即全新的空的visited）
beats 27.78%
class Solution:
def swimInWater(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
self.N = len(grid)
# self.visited = {}
left, right = grid[0][0], self.N * self.N - 1
while left < right:
mid = left + (right - left) // 2
if self.canReach(grid, mid, 0, 0, {}):
right = mid
else:
left = mid + 1
return left
def canReach(self, grid, time, i, j, visited):
visited[(i,j)] = 1
for x, y in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
new_i, new_j = i + x, j + y
if 0 <= new_i < self.N and 0 <= new_j < self.N and \
(new_i, new_j) not in visited and grid[new_i][new_j] <= time:
if new_i == new_j == self.N - 1:
return True
if self.canReach(grid, time, new_i, new_j, visited):
return True
return False