LeetCode 3341: Find Minimum Time to Reach Last Room I (Dijkstra with Waiting Time)
LeetCode 3341GraphDijkstraToday we solve LeetCode 3341 - Find Minimum Time to Reach Last Room I.
Source: https://leetcode.com/problems/find-minimum-time-to-reach-last-room-i/
English
Problem Summary
You are in a grid dungeon at room (0, 0) at time 0. Each room (i, j) has an opening time moveTime[i][j], meaning you can only start moving into that room at or after that time. Moving to an adjacent room costs exactly 1 second. Return the minimum time to reach the last room (n-1, m-1).
Key Idea
This is a shortest-path problem on a weighted grid graph. From current state (r, c, t), moving to neighbor (nr, nc) arrives at:
nextTime = max(t, moveTime[nr][nc]) + 1
Because edge costs are non-negative and depend on current best time, Dijkstra is the correct tool.
Algorithm
1) Let dist[r][c] be the best known arrival time.
2) Initialize dist[0][0] = 0, push (0,0,0) into min-heap.
3) Pop the smallest-time state; skip if stale.
4) Relax 4 neighbors with max(curTime, moveTime[nr][nc]) + 1.
5) First time we pop target cell, that time is optimal.
Complexity
Let V = n*m. Each cell is pushed a limited number of times and each pop/relax uses heap operations.
Time: O(V log V), Space: O(V).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.*;
class Solution {
public int minTimeToReach(int[][] moveTime) {
int n = moveTime.length, m = moveTime[0].length;
int[][] dist = new int[n][m];
for (int i = 0; i < n; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
dist[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[]{0, 0, 0}); // time, r, c
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int t = cur[0], r = cur[1], c = cur[2];
if (t != dist[r][c]) continue;
if (r == n - 1 && c == m - 1) return t;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
int nt = Math.max(t, moveTime[nr][nc]) + 1;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.offer(new int[]{nt, nr, nc});
}
}
}
return -1;
}
}package main
import "container/heap"
type Node struct{ t, r, c int }
type MinHeap []Node
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].t < h[j].t }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Node)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func minTimeToReach(moveTime [][]int) int {
n, m := len(moveTime), len(moveTime[0])
const INF = int(1e18)
dist := make([][]int, n)
for i := 0; i < n; i++ {
dist[i] = make([]int, m)
for j := 0; j < m; j++ {
dist[i][j] = INF
}
}
dist[0][0] = 0
h := &MinHeap{{0, 0, 0}}
heap.Init(h)
dr := [4]int{-1, 1, 0, 0}
dc := [4]int{0, 0, -1, 1}
for h.Len() > 0 {
cur := heap.Pop(h).(Node)
t, r, c := cur.t, cur.r, cur.c
if t != dist[r][c] {
continue
}
if r == n-1 && c == m-1 {
return t
}
for k := 0; k < 4; k++ {
nr, nc := r+dr[k], c+dc[k]
if nr < 0 || nr >= n || nc < 0 || nc >= m {
continue
}
nt := max(t, moveTime[nr][nc]) + 1
if nt < dist[nr][nc] {
dist[nr][nc] = nt
heap.Push(h, Node{nt, nr, nc})
}
}
}
return -1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTimeToReach(vector<vector<int>>& moveTime) {
int n = moveTime.size(), m = moveTime[0].size();
const int INF = 1e9;
vector<vector<int>> dist(n, vector<int>(m, INF));
dist[0][0] = 0;
using T = array<int, 3>; // time, r, c
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, 0, 0});
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
while (!pq.empty()) {
auto [t, r, c] = pq.top(); pq.pop();
if (t != dist[r][c]) continue;
if (r == n - 1 && c == m - 1) return t;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
int nt = max(t, moveTime[nr][nc]) + 1;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push({nt, nr, nc});
}
}
}
return -1;
}
};import heapq
from typing import List
class Solution:
def minTimeToReach(self, moveTime: List[List[int]]) -> int:
n, m = len(moveTime), len(moveTime[0])
INF = 10**30
dist = [[INF] * m for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)] # time, r, c
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while pq:
t, r, c = heapq.heappop(pq)
if t != dist[r][c]:
continue
if r == n - 1 and c == m - 1:
return t
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m:
nt = max(t, moveTime[nr][nc]) + 1
if nt < dist[nr][nc]:
dist[nr][nc] = nt
heapq.heappush(pq, (nt, nr, nc))
return -1class MinHeap {
constructor() { this.h = []; }
size() { return this.h.length; }
push(x) {
this.h.push(x);
this._up(this.h.length - 1);
}
pop() {
const n = this.h.length;
if (!n) return null;
this._swap(0, n - 1);
const ret = this.h.pop();
this._down(0);
return ret;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p][0] <= this.h[i][0]) break;
this._swap(i, p);
i = p;
}
}
_down(i) {
const n = this.h.length;
while (true) {
let l = i * 2 + 1, r = l + 1, s = i;
if (l < n && this.h[l][0] < this.h[s][0]) s = l;
if (r < n && this.h[r][0] < this.h[s][0]) s = r;
if (s === i) break;
this._swap(i, s);
i = s;
}
}
_swap(i, j) { [this.h[i], this.h[j]] = [this.h[j], this.h[i]]; }
}
var minTimeToReach = function(moveTime) {
const n = moveTime.length, m = moveTime[0].length;
const INF = Number.MAX_SAFE_INTEGER;
const dist = Array.from({ length: n }, () => Array(m).fill(INF));
dist[0][0] = 0;
const pq = new MinHeap();
pq.push([0, 0, 0]); // time, r, c
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
while (pq.size()) {
const [t, r, c] = pq.pop();
if (t !== dist[r][c]) continue;
if (r === n - 1 && c === m - 1) return t;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
const nt = Math.max(t, moveTime[nr][nc]) + 1;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push([nt, nr, nc]);
}
}
}
return -1;
};中文
题目概述
你在网格地牢的 (0,0)，初始时间为 0。每个房间 (i,j) 有开启时间 moveTime[i][j]，表示你只能在该时刻或之后开始进入该房间。移动到相邻房间耗时固定 1 秒。求到达终点 (n-1,m-1) 的最小时间。
核心思路
这是网格最短路。若当前在 (r,c) 的时间是 t，去相邻房间 (nr,nc) 的到达时间为：
nextTime = max(t, moveTime[nr][nc]) + 1
因为每条转移代价非负，用 Dijkstra 可以稳定得到全局最优。
算法步骤
1）dist[r][c] 记录到达每个格子的最小时间。
2）初始化 dist[0][0]=0，把起点放入小根堆。
3）每次弹出当前时间最小的状态，若是旧状态则跳过。
4）按四个方向做松弛，转移公式是 max(curTime, moveTime[nr][nc]) + 1。
5）终点第一次出堆时即为答案。
复杂度分析
设 V=n*m。时间复杂度 O(V log V)，空间复杂度 O(V)。
参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.*;
class Solution {
public int minTimeToReach(int[][] moveTime) {
int n = moveTime.length, m = moveTime[0].length;
int[][] dist = new int[n][m];
for (int i = 0; i < n; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
dist[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[]{0, 0, 0}); // time, r, c
int[] dr = {-1, 1, 0, 0};
int[] dc = {0, 0, -1, 1};
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int t = cur[0], r = cur[1], c = cur[2];
if (t != dist[r][c]) continue;
if (r == n - 1 && c == m - 1) return t;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
int nt = Math.max(t, moveTime[nr][nc]) + 1;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.offer(new int[]{nt, nr, nc});
}
}
}
return -1;
}
}package main
import "container/heap"
type Node struct{ t, r, c int }
type MinHeap []Node
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].t < h[j].t }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Node)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func minTimeToReach(moveTime [][]int) int {
n, m := len(moveTime), len(moveTime[0])
const INF = int(1e18)
dist := make([][]int, n)
for i := 0; i < n; i++ {
dist[i] = make([]int, m)
for j := 0; j < m; j++ {
dist[i][j] = INF
}
}
dist[0][0] = 0
h := &MinHeap{{0, 0, 0}}
heap.Init(h)
dr := [4]int{-1, 1, 0, 0}
dc := [4]int{0, 0, -1, 1}
for h.Len() > 0 {
cur := heap.Pop(h).(Node)
t, r, c := cur.t, cur.r, cur.c
if t != dist[r][c] {
continue
}
if r == n-1 && c == m-1 {
return t
}
for k := 0; k < 4; k++ {
nr, nc := r+dr[k], c+dc[k]
if nr < 0 || nr >= n || nc < 0 || nc >= m {
continue
}
nt := max(t, moveTime[nr][nc]) + 1
if nt < dist[nr][nc] {
dist[nr][nc] = nt
heap.Push(h, Node{nt, nr, nc})
}
}
}
return -1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTimeToReach(vector<vector<int>>& moveTime) {
int n = moveTime.size(), m = moveTime[0].size();
const int INF = 1e9;
vector<vector<int>> dist(n, vector<int>(m, INF));
dist[0][0] = 0;
using T = array<int, 3>; // time, r, c
priority_queue<T, vector<T>, greater<T>> pq;
pq.push({0, 0, 0});
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};
while (!pq.empty()) {
auto [t, r, c] = pq.top(); pq.pop();
if (t != dist[r][c]) continue;
if (r == n - 1 && c == m - 1) return t;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
int nt = max(t, moveTime[nr][nc]) + 1;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push({nt, nr, nc});
}
}
}
return -1;
}
};import heapq
from typing import List
class Solution:
def minTimeToReach(self, moveTime: List[List[int]]) -> int:
n, m = len(moveTime), len(moveTime[0])
INF = 10**30
dist = [[INF] * m for _ in range(n)]
dist[0][0] = 0
pq = [(0, 0, 0)] # time, r, c
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while pq:
t, r, c = heapq.heappop(pq)
if t != dist[r][c]:
continue
if r == n - 1 and c == m - 1:
return t
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m:
nt = max(t, moveTime[nr][nc]) + 1
if nt < dist[nr][nc]:
dist[nr][nc] = nt
heapq.heappush(pq, (nt, nr, nc))
return -1class MinHeap {
constructor() { this.h = []; }
size() { return this.h.length; }
push(x) {
this.h.push(x);
this._up(this.h.length - 1);
}
pop() {
const n = this.h.length;
if (!n) return null;
this._swap(0, n - 1);
const ret = this.h.pop();
this._down(0);
return ret;
}
_up(i) {
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p][0] <= this.h[i][0]) break;
this._swap(i, p);
i = p;
}
}
_down(i) {
const n = this.h.length;
while (true) {
let l = i * 2 + 1, r = l + 1, s = i;
if (l < n && this.h[l][0] < this.h[s][0]) s = l;
if (r < n && this.h[r][0] < this.h[s][0]) s = r;
if (s === i) break;
this._swap(i, s);
i = s;
}
}
_swap(i, j) { [this.h[i], this.h[j]] = [this.h[j], this.h[i]]; }
}
var minTimeToReach = function(moveTime) {
const n = moveTime.length, m = moveTime[0].length;
const INF = Number.MAX_SAFE_INTEGER;
const dist = Array.from({ length: n }, () => Array(m).fill(INF));
dist[0][0] = 0;
const pq = new MinHeap();
pq.push([0, 0, 0]); // time, r, c
const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
while (pq.size()) {
const [t, r, c] = pq.pop();
if (t !== dist[r][c]) continue;
if (r === n - 1 && c === m - 1) return t;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
const nt = Math.max(t, moveTime[nr][nc]) + 1;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push([nt, nr, nc]);
}
}
}
return -1;
};
Comments