【Leetcode 每日一题 - 扩展】3342. 到达最后一个房间的最少时间 II

问题背景

有一个地窖，地窖中有 $n\times m$ 个房间，它们呈网格状排布。
给你一个大小为 $n\times m$ 的二维数组 $moveTime$，其中 $moveTime[i][j]$ 表示在这个时刻 以后 你才可以 开始 往这个房间 移动 。你在时刻 $t=0$ 时从房间 $(0,0)$ 出发，每次可以移动到 相邻 的一个房间。在 相邻 房间之间移动需要的时间为：第一次花费 $1$ 秒，第二次花费 $2$ 秒，第三次花费 $1$ 秒，第四次花费 $2$ 秒……如此 往复 。
请你返回到达房间 $(n-1,m-1)$ 所需要的 最少 时间。
如果两个房间有一条公共边（可以是水平的也可以是竖直的），那么我们称这两个房间是 相邻 的。

数据约束

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

解题过程

Dijkstra 算法的模板题，需要修改的模板中新距离的计算方式。
另外有必要一提的是，题中要求的时间是出发时间而非到达时间，这是很容易出错的地方。

具体实现

class Solution {
    private final static int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length;
        int m = moveTime[0].length;

        int[][] dis = new int[n][m];
        for (int[] row : dis) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dis[0][0] = 0;

        PriorityQueue<int[]> heap = new PriorityQueue<>((o1, o2) -> o1[0] - o2[0]);
        heap.add(new int[]{0, 0, 0});

        while (true) {
            int[] cur = heap.poll();
            int d = cur[0], i = cur[1], j = cur[2];
            if (i == n - 1 && j == m - 1) {
                return d;
            }
            if (d > dis[i][j]) {
                continue;
            }
            int time = (i + j) % 2 + 1;
            for (int[] direction : DIRECTIONS) {
                int x = i + direction[0], y = j + direction[1];
                if (0 <= x && x < n && 0 <= y && y < m) {
                    int newDis = Math.max(d, moveTime[x][y]) + time;
                    if (newDis < dis[x][y]) {
                        dis[x][y] = newDis;
                        heap.add(new int[]{newDis, x, y});
                    }
                }
            }
        }
    }
}