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) 所用的最短时间。

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

2 <= n == moveTime.length <= 50。

2 <= m == moveTime[i].length <= 50。

0 <= moveTime[i][j] <= 1000000000。

输入：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)。

Go完整代码如下：

package main

import (
	"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 < 0 || nx >= n || ny < 0 || 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 []State

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].dis < pq[j].dis
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	x := old[n-1]
	*pq = old[:n-1]
	return x
}

func main() {
	moveTime := [][]int{{0, 4}, {4, 4}}
	result := minTimeToReach(moveTime)
	fmt.Println(result)
}

Python完整代码如下：

.

# -*-coding:utf-8-*-

import heapq
import math

def 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] = 0
    pq = [(0, 0, 0)]  # (dis, x, y)

    while pq:
        dis, x, y = heapq.heappop(pq)
        if visited[x][y]:
            continue
        visited[x][y] = True
        for dx, dy in dirs:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                dist = max(d[x][y], moveTime[nx][ny]) + 1
                if d[nx][ny] > dist:
                    d[nx][ny] = dist
                    heapq.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)