66 lines
2.0 KiB
Python
66 lines
2.0 KiB
Python
# Time: O(M · N)
|
|
# Space: O(M · N)
|
|
from collections import deque
|
|
|
|
class Solution:
|
|
def minimumEffortPath(self, heights: List[List[int]]) -> int:
|
|
'''
|
|
BFS + Binary Search
|
|
|
|
Give attention to definition of minimum effort in the problem.
|
|
It's not the total across the path, but just between two
|
|
adjacent allowed cells.
|
|
'''
|
|
nrows, ncols = len(heights), len(heights[0])
|
|
|
|
def can_reach_destination(mid):
|
|
'''
|
|
Do BFS traversing min paths
|
|
'''
|
|
visited = set()
|
|
q = deque([(0, 0)])
|
|
destination = (nrows - 1, ncols - 1)
|
|
|
|
while q:
|
|
x, y = q.popleft()
|
|
|
|
# See if we reached the destination
|
|
if (x, y) == destination:
|
|
return True
|
|
|
|
visited.add((x, y))
|
|
|
|
dirs = [
|
|
(0, 1), # Right
|
|
(0, -1), # Left
|
|
(1, 0), # Bottom
|
|
(-1, 0) # Top
|
|
]
|
|
|
|
for dx, dy in dirs:
|
|
adj_x = x + dx
|
|
adj_y = y + dy
|
|
|
|
if 0 <= adj_x < nrows and 0 <= adj_y < ncols and (adj_x, adj_y) not in visited:
|
|
if abs(heights[x][y] - heights[adj_x][adj_y]) <= mid:
|
|
visited.add((adj_x, adj_y))
|
|
q.append((adj_x, adj_y))
|
|
|
|
return False
|
|
|
|
left = 0
|
|
right = 1e6 # As provided in the problem statement
|
|
|
|
# Perform binary search
|
|
while left < right:
|
|
mid = (left + right) // 2
|
|
|
|
# The answer could either be mid or an effort value
|
|
# lower than mid
|
|
if can_reach_destination(mid):
|
|
right = mid
|
|
else:
|
|
left = mid + 1
|
|
|
|
return int(left)
|