Medium

题目描述

有一个由 n x m 个房间组成的网格地牢。

给你一个大小为 n x m 的二维数组 moveTime，其中 moveTime[i][j] 表示你可以开始移动到该房间的最小时间（以秒为单位）。你从房间 (0, 0) 在时间 t = 0 开始，可以移动到相邻的房间。在相邻房间之间移动，第一次移动需要 1 秒，下一次移动需要 2 秒，两者交替进行。

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

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

示例 1：

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

示例 2：

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

示例 3：

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

约束条件：

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

解题思路

这是一个带状态的最短路径问题。关键在于理解移动时间的交替规律：第一次移动需要1秒，第二次移动需要2秒，然后继续交替。

核心思路：

  1. 状态定义：我们需要跟踪当前位置和下一次移动所需的时间（1秒还是2秒）
  2. Dijkstra算法：使用优先队列找最短路径，状态为 (时间, 行, 列, 下次移动耗时)
  3. 时间计算：到达某个房间的实际时间为 max(当前时间 + 移动耗时, moveTime[i][j])
  4. 状态转移：每次移动后，下次移动的耗时在1和2之间交替

算法流程：

  • 从起点(0,0)开始，初始下次移动耗时为1
  • 对于每个当前状态，尝试向四个方向移动
  • 计算到达新位置的时间，考虑moveTime限制
  • 如果新状态的时间更短，则加入优先队列
  • 当第一次到达终点时，返回对应时间

推荐解法： 使用Dijkstra算法 + 状态压缩，时间复杂度最优。

代码实现

class Solution {
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n = moveTime.size(), m = moveTime[0].size();
        vector<vector<vector<int>>> dist(n, vector<vector<int>>(m, vector<int>(2, INT_MAX)));
        
        priority_queue<array<int, 4>, vector<array<int, 4>>, greater<>> pq;
        pq.push({0, 0, 0, 1}); // {time, row, col, next_move_time}
        dist[0][0][0] = 0;
        
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!pq.empty()) {
            auto [time, r, c, move_time] = pq.top();
            pq.pop();
            
            if (r == n - 1 && c == m - 1) return time;
            
            int state = move_time == 1 ? 0 : 1;
            if (time > dist[r][c][state]) continue;
            
            for (auto& dir : dirs) {
                int nr = r + dir[0], nc = c + dir[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                
                int new_time = max(time + move_time, moveTime[nr][nc]);
                int new_move_time = 3 - move_time;
                int new_state = new_move_time == 1 ? 0 : 1;
                
                if (new_time < dist[nr][nc][new_state]) {
                    dist[nr][nc][new_state] = new_time;
                    pq.push({new_time, nr, nc, new_move_time});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        dist = [[[float('inf')] * 2 for _ in range(m)] for _ in range(n)]
        
        pq = [(0, 0, 0, 1)]  # (time, row, col, next_move_time)
        dist[0][0][0] = 0
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while pq:
            time, r, c, move_time = heapq.heappop(pq)
            
            if r == n - 1 and c == m - 1:
                return time
            
            state = 0 if move_time == 1 else 1
            if time > dist[r][c][state]:
                continue
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < m:
                    new_time = max(time + move_time, moveTime[nr][nc])
                    new_move_time = 3 - move_time
                    new_state = 0 if new_move_time == 1 else 1
                    
                    if new_time < dist[nr][nc][new_state]:
                        dist[nr][nc][new_state] = new_time
                        heapq.heappush(pq, (new_time, nr, nc, new_move_time))
        
        return -1

public class Solution {
    public int MinTimeToReach(int[][] moveTime) {
        int n = moveTime.Length, m = moveTime[0].Length;
        int[,,] dist = new int[n, m, 2];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dist[i, j, 0] = dist[i, j, 1] = int.MaxValue;
            }
        }
        
        var pq = new PriorityQueue<(int time, int r, int c, int moveTime), int>();
        pq.Enqueue((0, 0, 0, 1), 0);
        dist[0, 0, 0] = 0;
        
        int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (pq.Count > 0) {
            var (time, r, c, moveTime) = pq.Dequeue();
            
            if (r == n - 1 && c == m - 1) return time;
            
            int state = moveTime == 1 ? 0 : 1;
            if (time > dist[r, c, state]) continue;
            
            for (int i = 0; i < 4; i++) {
                int nr = r + dirs[i, 0], nc = c + dirs[i, 1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;
                
                int newTime = Math.Max(time + moveTime, moveTime[nr][nc]);
                int newMoveTime = 3 - moveTime;
                int newState = newMoveTime == 1 ? 0 : 1;
                
                if (newTime < dist[nr, nc, newState]) {
                    dist[nr, nc, newState] = newTime;
                    pq.Enqueue((newTime, nr, nc, newMoveTime), newTime);
                }
            }
        }
        
        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 = new MinPriorityQueue({priority: x => x[0]});
    const dist = Array(n).fill().map(() => Array(m).fill(Infinity));
    
    pq.enqueue([0, 0, 0, 0]); // [time, row, col, moves]
    dist[0][0] = 0;
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    while (!pq.isEmpty()) {
        const [time, row, col, moves] = pq.dequeue().element;
        
        if (row === n - 1 && col === m - 1) {
            return time;
        }
        
        if (time > dist[row][col]) continue;
        
        for (const [dr, dc] of directions) {
            const nr = row + dr;
            const nc = col + dc;
            
            if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
                const moveCost = moves % 2 === 0 ? 1 : 2;
                let newTime = time + moveCost;
                
                if (newTime < moveTime[nr][nc]) {
                    const waitTime = moveTime[nr][nc] - newTime;
                    if (waitTime % 2 !== 0) {
                        newTime = moveTime[nr][nc] + 1;
                    } else {
                        newTime = moveTime[nr][nc];
                    }
                }
                
                if (newTime < dist[nr][nc]) {
                    dist[nr][nc] = newTime;
                    pq.enqueue([newTime, nr, nc, moves + 1]);
                }
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

解释：

  • 时间复杂度：每个位置有2个状态（下次移动1秒或2秒），总共2nm个状态，每个状态最多入队一次，优先队列操作为O(log(nm))
  • 空间复杂度：需要存储每个位置的两种状态的最短距离，以及优先队列的空间

相关题目