题目描述

有一个地窖，地窖中有 n x m 个房间，它们呈网格状排布。

给你一个大小为 n x m 的二维数组 moveTime，其中 moveTime[i][j] 表示在这个时刻 以后 你才可以 开始 往这个房间 移动。你在时刻 t = 0 时从房间 (0, 0) 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为：第一次花费 1 秒，第二次花费 2 秒，第三次花费 1 秒，第四次花费 2 秒……如此 往复。

请你返回到达房间 (n - 1, m - 1) 所需要的 最少 时间。

如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。

样例

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

输出：7

解释：

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

在时刻 t == 4，从房间 (0, 0) 移动到房间 (1, 0)，花费 1 秒。
在时刻 t == 5，从房间 (1, 0) 移动到房间 (1, 1)，花费 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 秒。

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

输出：4

限制

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

算法

(Dijkstra 最短路) $O(nm \log (nm))$

1. 可以通过 Dijkstra 算法计算出从起点走到 (i, j) 的最短路。
2. 从 (i, j) 走到相邻格子 (x, y)，到达 (x, y) 的时间为 $\max(dis(i, j), moveTime(i, j)) + ((x + y) \text{ mod } 2) + 1$。

时间复杂度

• 图的节点个数为 $O(nm)$，边的个数也为 $O(nm)$，故 Dijkstra 最短路算法的时间复杂度为 $O(nm \log (nm))$。

空间复杂度

• 需要 $O(nm)$ 的额外空间存储距离数组和堆。

C++ 代码

const int N = 750;

class Solution {
private:
    int dis[N][N];

public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        const int n = moveTime.size(), m = moveTime[0].size();

        const int dx[] = {0, 1, 0, -1};
        const int dy[] = {1, 0, -1, 0};

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                dis[i][j] = INT_MAX;

        dis[0][0] = 0;
        priority_queue<tuple<int, int, int>> heap;

        heap.push({0, 0, 0});

        while (!heap.empty()) {
            auto u = heap.top();
            heap.pop();

            int d = -get<0>(u);
            int x = get<1>(u), y = get<2>(u);

            if (d > dis[x][y])
                continue;

            for (int i = 0; i < 4; i++) {
                int tx = x + dx[i], ty = y + dy[i];
                if (tx < 0 || tx >= n || ty < 0 || ty >= m)
                    continue;

                int w = max(d, moveTime[tx][ty]) + ((x + y) & 1) + 1;
                if (dis[tx][ty] > w) {
                    dis[tx][ty] = w;
                    heap.push({-w, tx, ty});
                }
            }
        }

        return dis[n - 1][m - 1];
    }
};