文章目录
3342.到达最后一个房间的最少时间II
- 思路分析：
最短路径问题，当然，由于不同的格子之间的移动的代价不统一,所以这个最短路径需要使用Dijkstra算法进行求解，对于直接使用Dijkstra算法模版的题目，大家可以先去做一下3341. 到达最后一个房间的最少时间 I - 这个题目难点在于
如何计算从格子(x,y)出发的代价是1还是2
- 通过画出具体的转移代价的图，我们发现是有规律的，当当前位于
(x,y)的时候，转移的代码可以表示为(x+y)%2 + 1,既然得出了代价的计算，那么接下来直接套用Dijkstra算法的模版即可
import heapq
class Solution:def minTimeToReach(self, moveTime: List[List[int]]) -> int:n,m = len(moveTime),len(moveTime[0])dis = [[float("inf")]*m for _ in range(n)]dis[0][0] = 0 h = [(0,(0,0))]tmp = []cou = 1step = [(0,-1),(0,1),(-1,0),(1,0)]# 感觉得来一个中转的while h:d,(x,y) = heapq.heappop(h)if d > dis[x][y]:continueif x == n-1 and y == m-1:return d # 访问邻居# 处理十分巧妙time = (x+y) % 2 + 1for dx,dy in step:nx,ny = x+dx,y+dy if 0<=nx<n and 0<=ny<m:newdis = d + time if d + time > moveTime[nx][ny] + time else moveTime[nx][ny] + timeif newdis < dis[nx][ny]:dis[nx][ny] = newdisheapq.heappush(h,(newdis,(nx,ny)))
