LeetCode 3341到达最后一个房间的最少时间 I 题解

这题是一道比较典型的bfs，但是题目会在此基础上加一些限制，先给出示例和图示让大家更容易理解这题的思路

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

典型的bfs只是要边bfs的时候边判断t是需要wait后加1还是直接加1，对于此题我们不仅仅可以使用bfs也可以使用Dijkstra，Dijkstra的逻辑感可能更强些，但是会用到一个我平常不怎么使用的函数式子。

先来看看Dijkstra的示例实现，分步说说刚好巩固自身对于该方法的使用，因为我也不太熟悉。

先建立上、下、左、右的走步坐标系

int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

然后建立队列存放数据，但这个队列有些不同，它不是先进先出(FIFO)类型的队列，而是根据数组第一个值的大小决定，最小的值先出栈

PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

这里解释很简单，就是初始化一下坐标的开始位置{t,x,y}，t表示抵达(x,y)位置的时间,将这三个值一起记录下来方便遍历比较

heap.offer(new int[]{0, 0, 0});

这里的话算是一种打标记，记录每个位置的抵达时间，如果有比初始的值小的就替换然后进栈遍历后续节点

int n = moveTime.length, m = moveTime[0].length;
// time[i][j]表示到达(i,j)的最少时间
int[][] time = new int[n][m];
for (int i = 0; i < n; i++) {Arrays.fill(time[i], Integer.MAX_VALUE);
}
time[0][0] = 0; // 初始化

这里就是Dijkstra最关键的一个部分，先来解释一下这里的代码，将初始节点和后续节点抛出（选取最小的t节点）对于t>time[x][y]的值是因为之前遍历过了(x,y)这个节点且其对应的抵达时间相较于当前的t更小，所以不需要继续往下了
举个例子：
假设当前到 (1,1) 有两条路径：

• 一条需要时间 10，先入队。

• 后来发现另一条更优路径，时间为 6，也入队。

此时队列中两个 (1,1)：

[ (6, 1, 1), (10, 1, 1) ]

• 6 的那条先处理，更新时间为 6

• 再处理 10 的那条，因为你之前已经更新为 6，所以直接跳过。

  if (t > time[x][y]) continue; // 剪枝

如果不剪枝会怎么样？

• 会再次访问 (1,1)，重复处理邻居，导致不必要的入队操作，性能变差。

while (!heap.isEmpty()) {int[] curr = heap.poll();int t = curr[0], x = curr[1], y = curr[2];if (t > time[x][y]) { // 剪枝continue;}for (int[] dir : dirs) {int nx = x + dir[0], ny = y + dir[1];if (0 <= nx && nx < n && 0 <= ny && ny < m) {int nt;if (t < moveTime[nx][ny]) { // 需要等待nt = 1 + moveTime[nx][ny];} else { // 否则，直接进入nt = t + 1;}if (nt < time[nx][ny]) { // 当前的更优路径time[nx][ny] = nt;heap.offer(new int[]{nt, nx, ny});}}}}

之后就是进入bfs的遍历进行判断当前节点向四周延申的节点是需要等待后才能进入还是可以直接进入，并更新路径time[nx][ny],以便后续的节点遍历至相同节点进行对比抵达时间然后更新。

最后return time[n-1][m-1]即可

以下是完整代码

class Solution {public int minTimeToReach(int[][] moveTime) {// Dijkstra，并允许同一个节点的重复访问int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};// 最小堆，存储数组 {t, x, y}，表示到达 (x, y) 的时间为 tPriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);// 起点heap.offer(new int[]{0, 0, 0});int n = moveTime.length, m = moveTime[0].length;// time[i][j]表示到达(i,j)的最少时间int[][] time = new int[n][m];for (int i = 0; i < n; i++) {Arrays.fill(time[i], Integer.MAX_VALUE);}time[0][0] = 0; // 初始化while (!heap.isEmpty()) {int[] curr = heap.poll();int t = curr[0], x = curr[1], y = curr[2];if (t > time[x][y]) { // 剪枝continue;}for (int[] dir : dirs) {int nx = x + dir[0], ny = y + dir[1];if (0 <= nx && nx < n && 0 <= ny && ny < m) {int nt;if (t < moveTime[nx][ny]) { // 需要等待nt = 1 + moveTime[nx][ny];} else { // 否则，直接进入nt = t + 1;}if (nt < time[nx][ny]) { // 当前的更优路径time[nx][ny] = nt;heap.offer(new int[]{nt, nx, ny});}}}}return time[n - 1][m - 1]; // 终点}
}

这是用了方法优先队列对此题的优解，也可以使用传统的bfs队列，只是会时间用的更长一些

class Solution {public int minTimeToReach(int[][] moveTime) {int n = moveTime.length, m = moveTime[0].length;int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};// 初始化距离矩阵int[][] dist = new int[n][m];for (int i = 0; i < n; i++) {Arrays.fill(dist[i], Integer.MAX_VALUE);}dist[0][0] = 0;// 使用双端队列进行BFSDeque<int[]> q = new ArrayDeque<>();q.offer(new int[]{0, 0});while (!q.isEmpty()) {int[] curr = q.poll();int i = curr[0], j = curr[1];for (int[] dir : dirs) {int ni = i + dir[0], nj = j + dir[1];if (ni >= 0 && ni < n && nj >= 0 && nj < m) {// 计算从(i,j)到达(ni,nj)的最早时间int newTime = Math.max(dist[i][j], moveTime[ni][nj]) + 1;// 如果找到更优路径，更新并加入队列if (newTime < dist[ni][nj]) {dist[ni][nj] = newTime;q.offer(new int[]{ni, nj});}}}}return dist[n - 1][m - 1];}
}

也一样需要一个二维数组去存抵达时间的值，然后更新最小的抵达时间，这个应该比上一个更容易理解，不想再解释了…