Medium

题目描述

有一个包含 n x m 个房间的地牢，房间按网格排列。

给你一个大小为 n x m 的二维数组 moveTime，其中 moveTime[i][j] 表示房间开启并可以移动到该房间所需的最少时间（以秒为单位）。你从房间 (0, 0) 开始，时间 t = 0，可以移动到相邻的房间。在相邻房间之间移动恰好需要一秒钟。

返回到达房间 (n - 1, m - 1) 的最短时间。

如果两个房间在水平或垂直方向上共享一面墙，则它们是相邻的。

示例 1：

输入：moveTime = [[0,4],[4,4]]
输出：6
解释：
所需的最少时间为 6 秒。
- 在时间 t == 4，从房间 (0, 0) 移动到房间 (1, 0)，用时一秒。
- 在时间 t == 5，从房间 (1, 0) 移动到房间 (1, 1)，用时一秒。

示例 2：

输入：moveTime = [[0,0,0],[0,0,0]]
输出：3
解释：
所需的最少时间为 3 秒。
- 在时间 t == 0，从房间 (0, 0) 移动到房间 (1, 0)，用时一秒。
- 在时间 t == 1，从房间 (1, 0) 移动到房间 (1, 1)，用时一秒。
- 在时间 t == 2，从房间 (1, 1) 移动到房间 (1, 2)，用时一秒。

示例 3：

输入：moveTime = [[0,1],[1,2]]
输出：3

约束条件：

  • 2 <= n == moveTime.length <= 50
  • 2 <= m == moveTime[i].length <= 50
  • 0 <= moveTime[i][j] <= 10^9

解题思路

这是一个最短路径问题的变种，需要考虑时间约束。核心思路是使用 Dijkstra 算法。

关键观察：

  1. 我们不能在房间开启之前进入该房间
  2. 如果我们在房间开启时间之前到达，需要等待
  3. 如果我们可以通过在相邻房间来回移动来"消耗时间"，那么到达时间的奇偶性很重要

算法步骤：

  1. 使用优先队列（最小堆）维护 (到达时间, 行, 列)
  2. 对于每个相邻房间，计算到达时间：
    • 如果当前时间 + 1 >= moveTime[nx][ny]，直接移动
    • 否则需要等待到 moveTime[nx][ny]，但还要考虑奇偶性
  3. 奇偶性处理：如果等待时间与当前时间的奇偶性不同，需要额外等待1秒

特殊情况处理：

  • 如果起始位置的相邻房间都无法在合理时间内到达，需要特殊处理

这种方法确保找到全局最优解，时间复杂度为 O(nm log(nm))。

代码实现

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size(), m = moveTime[0].size();
        vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> pq;
        
        dist[0][0] = 0;
        pq.push({0, 0, 0});
        
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (!pq.empty()) {
            auto [time, x, y] = pq.top();
            pq.pop();
            
            if (x == n - 1 && y == m - 1) {
                return time;
            }
            
            if (time > dist[x][y]) continue;
            
            for (auto& dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                
                int nextTime = max(time + 1, moveTime[nx][ny]);
                if ((nextTime - time) % 2 == 0) {
                    nextTime++;
                }
                
                if (nextTime < dist[nx][ny]) {
                    dist[nx][ny] = nextTime;
                    pq.push({nextTime, nx, ny});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        import heapq
        
        n, m = len(moveTime), len(moveTime[0])
        dist = [[float('inf')] * m for _ in range(n)]
        pq = [(0, 0, 0)]  # (time, x, y)
        dist[0][0] = 0
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        
        while pq:
            time, x, y = heapq.heappop(pq)
            
            if x == n - 1 and y == m - 1:
                return time
            
            if time > dist[x][y]:
                continue
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m:
                    next_time = max(time + 1, moveTime[nx][ny])
                    if (next_time - time) % 2 == 0:
                        next_time += 1
                    
                    if next_time < dist[nx][ny]:
                        dist[nx][ny] = next_time
                        heapq.heappush(pq, (next_time, nx, ny))
        
        return -1

public 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++) {
            for (int j = 0; j < m; j++) {
                dist[i, j] = int.MaxValue;
            }
        }
        
        var pq = new PriorityQueue<(int time, int x, int y), int>();
        dist[0, 0] = 0;
        pq.Enqueue((0, 0, 0), 0);
        
        int[,] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        while (pq.Count > 0) {
            var (time, x, y) = pq.Dequeue();
            
            if (x == n - 1 && y == m - 1) {
                return time;
            }
            
            if (time > dist[x, y]) continue;
            
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d, 0], ny = y + dirs[d, 1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                
                int nextTime = Math.Max(time + 1, moveTime[nx][ny]);
                if ((nextTime - time) % 2 == 0) {
                    nextTime++;
                }
                
                if (nextTime < dist[nx, ny]) {
                    dist[nx, ny] = nextTime;
                    pq.Enqueue((nextTime, nx, ny), nextTime);
                }
            }
        }
        
        return -1;
    }
}

var minTimeToReach = function(moveTime) {
    const n = moveTime.length;
    const m = moveTime[0].length;
    
    if (moveTime[0][1] > 1 && moveTime[1][0] > 1) {
        return -1;
    }
    
    const pq = [[0, 0, 0]];
    const visited = new Set();
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [time, row, col] = pq.shift();
        
        if (row === n - 1 && col === m - 1) {
            return time;
        }
        
        const key = `${row},${col}`;
        if (visited.has(key)) {
            continue;
        }
        visited.add(key);
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m) {
                const key2 = `${newRow},${newCol}`;
                if (!visited.has(key2)) {
                    let newTime = Math.max(time + 1, moveTime[newRow][newCol]);
                    if (newTime > moveTime[newRow][newCol] && (newTime - time) % 2 === 0) {
                        newTime++;
                    }
                    pq.push([newTime, newRow, newCol]);
                }
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(nm log(nm))
空间复杂度O(nm)

其中 n 和 m 分别是网格的行数和列数。时间复杂度主要来自 Dijkstra 算法中优先队列的操作，空间复杂度用于存储距离数组和优先队列。

相关题目