3341. Find Minimum Time to Reach Last Room I
https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/description/
def minTimeToReach(self, moveTime: List[List[int]]) -> int:
m, n = len(moveTime), len(moveTime[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = 1
dq = [(0, 0, 0)]
direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while dq:
t, x, y = heapq.heappop(dq)
if x == m - 1 and y == n - 1:
return t
for dx, dy in direc:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < m and 0 <= new_y < n and dp[new_x][new_y] == 0:
dp[new_x][new_y] = 1
heapq.heappush(dq, (max(t, moveTime[new_x][new_y])+1, new_x, new_y))1631. Path With Minimum Effort
https://leetcode.com/problems/path-with-minimum-effort/description/
def minimumEffortPath(self, heights: List[List[int]]) -> int:
m, n = len(heights), len(heights[0])
dp = [[0] * n for _ in range(m)]
dq = [(0, 0, 0)]
direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while dq:
t, x, y = heapq.heappop(dq)
if dp[x][y] == 0:
dp[x][y] = 1
else:
continue
cur = heights[x][y]
if x == m - 1 and y == n - 1:
return t
for dx, dy in direc:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < m and 0 <= new_y < n and dp[new_x][new_y] == 0:
heapq.heappush(dq, (max(t, abs(heights[new_x][new_y]-cur)), new_x, new_y))2577. Minimum Time to Visit a Cell In a Grid
这个稍微难一点 但如果想明白每一步强迫走的实现方法就简单很多
class Solution:
def minimumTime(self, grid: List[List[int]]) -> int:
if grid[0][1] > 1 and grid[1][0] > 1:
return -1
n = len(grid)
m = len(grid[0])
dp = [[0] * m for _ in range(n)]
dq = [(0, 0, 0)]
direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while dq:
# print(dq)
t, x, y = heapq.heappop(dq)
if dp[x][y] == 0:
dp[x][y] = 1
else:
continue
if x == n - 1 and y == m - 1:
return t
for dx, dy in direc:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < n and 0 <= new_y < m and dp[new_x][new_y] == 0:
if grid[new_x][new_y] <= t + 1:
heapq.heappush(dq, (t + 1 , new_x, new_y))
else:
new_t = grid[new_x][new_y] if (grid[new_x][new_y] - t) % 2 == 1 else grid[new_x][new_y] + 1
heapq.heappush(dq, (new_t , new_x, new_y))
return -1
3286. Find a Safe Walk Through a Grid
https://leetcode.com/problems/find-a-safe-walk-through-a-grid/description/
跟前几个一模一样 比较简单 就不放了
1293. Shortest Path in a Grid with Obstacles Elimination
https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/description/
0-1 BFS 详情可见Dijkstra’s -→ 0-1 BFS(当edge为0或1时)
使用deque 根据当前行动接近目标选择添加前面还是后面 添加前面有可能遇到obs 也有可能没有 但是这一策略使算法永远向着最短路径前进 如果条件不满足(obs数量超过) 再去考虑要走更远但是没有遇到obs的路径
注意while里的第一个if 现在total_obs(这里是用k-经过的obs 也就是还剩的容错数)必须要大于此前记录的 如果小于等于 那么之前没有找到的结果现在更不可能找到(因为现在不光步数比之前记录时的长 obs容错也没有优势 整体肯定是更差的路径)
而 0 <= obs - grid[new_x][new_y] 则不需要考虑太多 只要不超过容错随便添加
def shortestPath(self, grid: List[List[int]], k: int) -> int:
n = len(grid)
m = len(grid[0])
dp = [[-float('inf')] * m for _ in range(n)]
dq = deque([(0, k, 0, 0)])
direc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while dq:
s, obs, x, y = dq.popleft()
if obs > dp[x][y]:
dp[x][y] = obs
if x == n - 1 and y == m - 1:
return s
for dx, dy in direc:
new_x, new_y = x + dx, y + dy
if 0 <= new_x < n and 0 <= new_y < m and 0 <= obs - grid[new_x][new_y]:
if dx == -1 or dy == 1:
dq.appendleft((s + 1, obs - grid[new_x][new_y], new_x, new_y))
else:
dq.append((s + 1, obs - grid[new_x][new_y], new_x, new_y))
return -1