在网格图中访问一个格子的最少时间

You are given a m x n matrix grid consisting of non-negative integers where grid[row][col] represents the minimum time required to be able to visit the cell (row, col), which means you can visit the cell (row, col) only when the time you visit it is greater than or equal to grid[row][col].

You are standing in the top-left cell of the matrix in the 0th second, and you must move to any adjacent cell in the four directions: up, down, left, and right. Each move you make takes 1 second.

Return the minimum time required in which you can visit the bottom-right cell of the matrix. If you cannot visit the bottom-right cell, then return -1.

 

Example 1:

Input: grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
Output: 7
Explanation: One of the paths that we can take is the following:
- at t = 0, we are on the cell (0,0).
- at t = 1, we move to the cell (0,1). It is possible because grid[0][1] <= 1.
- at t = 2, we move to the cell (1,1). It is possible because grid[1][1] <= 2.
- at t = 3, we move to the cell (1,2). It is possible because grid[1][2] <= 3.
- at t = 4, we move to the cell (1,1). It is possible because grid[1][1] <= 4.
- at t = 5, we move to the cell (1,2). It is possible because grid[1][2] <= 5.
- at t = 6, we move to the cell (1,3). It is possible because grid[1][3] <= 6.
- at t = 7, we move to the cell (2,3). It is possible because grid[2][3] <= 7.
The final time is 7. It can be shown that it is the minimum time possible.

Example 2:

Input: grid = [[0,2,4],[3,2,1],[1,0,4]]
Output: -1
Explanation: There is no path from the top left to the bottom-right cell.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 1000
• 4 <= m * n <= 105
• 0 <= grid[i][j] <= 105
• grid[0][0] == 0

 

/*
 * 思路：
 * 1. 使用广度优先搜索（BFS）来寻找从左上角到右下角的最早时间。
 * 2. 使用一个优先级队列来存储和处理当前能够到达的格子，优先访问时间最小的格子。
 * 3. 对每个格子，检查其四个方向的相邻格子，如果可以在当前时间+1时刻访问，加入队列继续搜索。
 * 4. 记录访问过的格子，避免重复访问。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int earliestArrivalTime(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[2]));
        boolean[][] visited = new boolean[m][n];
        pq.offer(new int[]{0, 0, 0});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int x = curr[0], y = curr[1], time = curr[2];
            if (x == m - 1 && y == n - 1) return time;
            if (visited[x][y]) continue;
            visited[x][y] = true;

            Arrays.stream(directions)
                .map(dir -> new int[]{x + dir[0], y + dir[1]})
                .filter(pos -> pos[0] >= 0 && pos[0] < m && pos[1] >= 0 && pos[1] < n && !visited[pos[0]][pos[1]])
                .forEach(pos -> pq.offer(new int[]{pos[0], pos[1], Math.max(time + 1, grid[pos[0]][pos[1]])}));
        }
        return -1;
    }
}

这道题目利用的是优先队列（最小堆）的方式来找出最早到达矩阵右下角的路径。算法开始时，将起始点 (0, 0) 的时间为 0 加入堆中。然后，依次从堆中取出当前时间最小的点，更新它的邻居节点。如果移动到邻居节点的时间小于该邻居节点在 grid 中指定的最早可访问时间，那么我们需要等待，直到满足条件。我们不断地从堆中取点和更新点，直到到达矩阵的右下角。如果在某个点的时间超过了我们在此之前访问过该点的时间，就无需再处理它。这是因为我们已经找到了一种更早到达该点的方式。如果我们在堆为空时还没有到达终点，说明无法到达终点，返回 -1。

O((m*n) * log(m*n))

O(m*n)