Hard
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:
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
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
public int minimumTime(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
if (grid[0][1] > 1 && grid[1][0] > 1) {
return -1;
}
PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.time));
pq.add(new Node(0, 0, 0));
int[] xDir = {0, 0, 1, -1};
int[] yDir = {1, -1, 0, 0};
int[][] vis = new int[m][n];
for (int[] temp : vis) {
Arrays.fill(temp, -1);
}
while (!pq.isEmpty()) {
Node curr = pq.remove();
if (curr.x == m - 1 && curr.y == n - 1) {
return curr.time;
}
vis[curr.x][curr.y] = 1;
int currTime = curr.time + 1;
for (int i = 0; i < 4; i++) {
int newX = curr.x + xDir[i];
int newY = curr.y + yDir[i];
if (newX >= 0 && newY >= 0 && newX < m && newY < n && vis[newX][newY] == -1) {
vis[newX][newY] = 1;
if (grid[newX][newY] <= currTime) {
pq.add(new Node(newX, newY, currTime));
} else {
if ((grid[newX][newY] - curr.time) % 2 == 0) {
pq.add(new Node(newX, newY, grid[newX][newY] + 1));
} else {
pq.add(new Node(newX, newY, grid[newX][newY]));
}
}
}
}
}
return -1;
}
private static class Node {
int x;
int y;
int time;
Node(int xx, int yy, int tt) {
x = xx;
y = yy;
time = tt;
}
}
}