- 矩阵数字是0-n^2-1的全排列,最终答案一定是这之中的某一个数字,用二分依次判断每一个数字是否能连通(0,0)-> (m-1,n-1), 连通性通过dfs/bfs/union find都可以判断
class Solution:
'''
Question:
Input - grid of elevation, List[List[int]],
the grid can't be null, each value are unique, value - [0, n2-1]
Output - int, the least time (0,0) -> (m-1, n-1)
Main Idea: Binary Search + DFS
Use Binary Seach to find which time can connect 0,0 -> (m-1,n-1)
Use DFS to go through the grid
Time Complexity: O(n2logn)
Space Complexity: O(n2), the size of stack
'''
def swimInWater(self, grid: List[List[int]]) -> int:
def check_connection(time: int) -> bool:
if time < grid[0][0]:
return False
visited = set()
return dfs(0,0,time, visited)
def dfs(x,y,time, visited) -> bool:
d = [(0,1),(0,-1),(-1,0),(1,0)]
in_bound = lambda x,y : 0<=x<n and 0<=y<n
if x== n-1 and y == n-1:
return True
visited.add((x,y))
for k in range(4):
a = x + d[k][0]
b = y + d[k][1]
if in_bound(a,b) and (a,b) not in visited and grid[a][b] <= time:
if dfs(a,b,time, visited):
return True
return False
n = len(grid)
left, right = 0, n**2-1
while left < right:
mid = (left +right) // 2
if check_connection(mid):
right = mid
else:
left = mid + 1
return left
DFS - Iterative:
def swimInWater(self, grid: List[List[int]]) -> int:
def check_connection(time: int) -> bool:
if time < grid[0][0]:
return False
visited = set()
stack = [(0,0)]
d = [(0,1),(0,-1),(-1,0),(1,0)]
in_bound = lambda x,y : 0<=x<n and 0<=y<n
while stack:
x, y = stack.pop()
if x== n-1 and y == n-1:
return True
visited.add((x,y))
for k in range(4):
a = x + d[k][0]
b = y + d[k][1]
if in_bound(a,b) and (a,b) not in visited and grid[a][b] <= time:
stack.append((a,b))
visited.add((a,b))
return False
n = len(grid)
left, right = 0, n**2-1
while left < right:
mid = (left +right) // 2
if check_connection(mid):
right = mid
else:
left = mid + 1
return left