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

摘要：给定一个 n x m 的二维数组 moveTime，其中 moveTime[i][j] 表示第 i 行第 j 列的房间开始可进入（即房门打开）所需的最早时间（以秒为单位）。你从时间点 t=0 时刻出发，起点是左上角的房间 (0, 0)。每次移动只能到上下左右相

2025-05-28：到达最后一个房间的最少时间Ⅰ。用go语言，你有一个地窖，里面由 n 行 m 列共 n*m 个房间组成，排列成一个网格。

给定一个 n x m 的二维数组 moveTime，其中 moveTime[i][j] 表示第 i 行第 j 列的房间开始可进入（即房门打开）所需的最早时间（以秒为单位）。你从时间点 t=0 时刻出发，起点是左上角的房间 (0, 0)。每次移动只能到上下左右相邻的房间，且移动到相邻房间需要 1 秒。

你的任务是计算：到达右下角房间 (n-1, m-1) 所用的最短时间。

这里定义的“相邻房间”是指共享一条边的房间，包括横向和纵向邻接。

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

输出：6。

解释：

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

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

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

题目来自力扣3341。

1. 初始化：• 获取地窖的行数 n 和列数 m。• 创建两个二维数组 d 和 v：• d[i][j] 表示到达房间 (i, j) 的最短时间，初始时所有值设为 math.MaxInt32（表示无穷大），除了起点 (0, 0) 设为 0。• v[i][j] 表示房间 (i, j) 是否已经被访问过，初始时所有值设为 false。• 定义四个移动方向：上下左右（dirs）。• 初始化一个优先队列（最小堆），并将起点 (0, 0, 0) 加入队列。2. Dijkstra 算法主循环：• 从优先队列中取出当前距离最短的节点 s（即 dis 最小的 State）。• 如果 s 已经被访问过（v[s.x][s.y] == true），则跳过。• 否则，标记 s 为已访问（v[s.x][s.y] = true）。• 遍历 s 的四个邻居：• 检查邻居是否在地窖范围内（即坐标是否合法）。• 计算从 s 到邻居的新距离 dist：• 新距离为 max(d[s.x][s.y], moveTime[nx][ny]) + 1。• 这里的 max 表示需要等待邻居房间可进入的时间（moveTime[nx][ny]）和当前到达 s 的时间（d[s.x][s.y]）的较大值，再加上移动的 1 秒。• 如果新距离比邻居的当前最短距离 d[nx][ny] 更小，则更新 d[nx][ny] 并将邻居加入优先队列。3. 终止条件：• 当优先队列为空或右下角房间 (n-1, m-1) 被访问时，算法结束。• 最终返回 d[n-1][m-1] 作为到达右下角房间的最短时间。• 时间复杂度：• 每个房间最多被访问一次，每次访问需要处理 4 个邻居。• 优先队列的插入和弹出操作的时间复杂度为 O(log(N))，其中 N 是队列中的元素数量（最多为 O(n*m)）。• 总时间复杂度为 O(n * m * log(n * m))。• 空间复杂度：• 需要存储 d 和 v 数组，大小为 O(n * m)。• 优先队列最多存储 O(n * m) 个元素。• 总空间复杂度为 O(n * m)。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 } 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]) + 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 min_time_to_reach(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)] # (dis, x, y)while pq:dis, x, y = heapq.heappop(pq)if visited[x][y]:continuevisited[x][y] = Truefor dx, dy in dirs:nx, ny = x + dx, y + dyif 0 dist:d[nx][ny] = distheapq.heappush(pq, (dist, nx, ny))return d[n-1][m-1]if __name__ == "__main__":moveTime = [[0, 4], [4, 4]]result = min_time_to_reach(moveTime)print(result)