2025-05-29：到达最后一个房间的最少时间Ⅱ 用go语言，你有一个

摘要：你从时刻 t=0 的房间 (0, 0) 出发，每次移动只能到相邻（上下左右边相连）的房间。移动所花费的时间有规律，第一次移动用 1 秒，第二次移动用 2 秒，第三次移动又是 1 秒，第四次是 2 秒，依此类推，移动时间在 1 秒和 2 秒之间交替。

2025-05-29：到达最后一个房间的最少时间Ⅱ。用go语言，你有一个大小为 n 行 m 列的地窖，每个格子代表一个房间，房间按网格排列。

给定一个二维数组 moveTime，大小为 n x m，moveTime[i][j] 表示你必须等到该时间点及之后才能开始进入房间 (i, j)。

你从时刻 t=0 的房间 (0, 0) 出发，每次移动只能到相邻（上下左右边相连）的房间。移动所花费的时间有规律，第一次移动用 1 秒，第二次移动用 2 秒，第三次移动又是 1 秒，第四次是 2 秒，依此类推，移动时间在 1 秒和 2 秒之间交替。

要求计算从起点 (0,0) 出发，到终点房间 (n-1, m-1) 所需要的最短总时间。

相邻房间是指两房间间有共同的边，无论是水平还是垂直方向。

输入：moveTime = [[0,4],[4,4]]。

输出：7。

解释：

需要花费的最少时间为 7 秒。

在时刻 t == 4 ，从房间 (0, 0) 移动到房间 (1, 0) ，花费 1 秒。

在时刻 t == 5 ，从房间 (1, 0) 移动到房间 (1, 1) ，花费 2 秒。

题目来自力扣3342。

1. 初始化：• 创建一个距离矩阵 d，大小为 n x m，初始值为无穷大（表示尚未到达），d[0][0] = 0（起点时间为 0）。• 创建一个访问矩阵 v，大小为 n x m，初始值为 false，表示是否已处理过该房间。• 使用优先队列（最小堆）来存储待处理的房间状态，初始时将起点 (0, 0, 0) 加入队列。2. 优先队列处理：• 从队列中取出当前距离最小的状态 (x, y, dis)。• 如果 (x, y) 是终点，直接返回 dis。• 如果 (x, y) 已访问过，跳过。• 标记 (x, y) 为已访问。3. 邻居处理：• 遍历当前房间的四个邻居 (nx, ny)。• 检查邻居是否在地窖范围内。• 计算到达邻居的新时间：• 移动时间：根据移动次数的奇偶性决定是 1 秒还是 2 秒。移动次数由 (x + y) 的奇偶性决定（因为每次移动会改变奇偶性）。• 新时间 dist = max(d[x][y], moveTime[nx][ny]) + ((x + y) % 2 + 1)。• (x + y) % 2 + 1 的值交替为 1 或 2。• 如果新时间比当前记录的 d[nx][ny] 更小，则更新 d[nx][ny] 并将 (nx, ny, dist) 加入队列。4. 终止条件：• 当优先队列为空或终点被访问时终止。package mainimport ( "container/heap" "fmt" "math")func minTimeToReach(moveTime int)int { n, m := len(moveTime), len(moveTime[0]) d := make(int, n) v := make(bool, n) for i := range d { d[i] = make(int, m) v[i] = make(bool, m) for j := range d[i] { d[i][j] = math.MaxInt32 } } dirs := int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} d[0][0] = 0 q := &PriorityQueue{} heap.Push(q, &State{0, 0, 0}) for q.Len > 0 { s := heap.Pop(q).(*State) if v[s.x][s.y] { continue } if s.x == n-1 && s.y == m-1 { break } v[s.x][s.y] = true for _, dir := range dirs { nx, ny := s.x+dir[0], s.y+dir[1] if nx = n || ny = m { continue } dist := max(d[s.x][s.y], moveTime[nx][ny]) + (s.x+s.y)%2 + 1 if d[nx][ny] > dist { d[nx][ny] = dist heap.Push(q, &State{nx, ny, dist}) } } } return d[n-1][m-1]}type State struct { x, y, dis int}type PriorityQueue *Statefunc (pq PriorityQueue) Len int { returnlen(pq)}func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dis

# -*-coding:utf-8-*-import heapqimport mathdef minTimeToReach(moveTime):n, m = len(moveTime), len(moveTime[0])d = [[math.inf] * m for _ in range(n)]visited = [[False] * m for _ in range(n)]dirs = [(1,0), (-1,0), (0,1), (0,-1)]d[0][0] = 0pq = [(0, 0, 0)] # (distance, x, y)while pq:dist, x, y = heapq.heappop(pq)if visited[x][y]:continueif x == n-1 and y == m-1:# 找到终点，结束breakvisited[x][y] = Truefor dx, dy in dirs:nx, ny = x + dx, y + dyif 0 nd:d[nx][ny] = ndheapq.heappush(pq, (nd, nx, ny))return d[n-1][m-1]# 测试样例moveTime = [[0, 4], [4, 4]]result = minTimeToReach(moveTime)print(result)