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.PriorityQueue
class Solution {
fun minimumTime(grid: Array<IntArray>): Int {
if (grid[0][1] <= 1 || grid[1][0] <= 1) {
val m = grid.size
val n = grid[0].size
val pq = PriorityQueue { a: IntArray, b: IntArray ->
a[0] - b[0]
}
val dist: MutableMap<String, Int> = HashMap()
pq.offer(intArrayOf(0, 0, 0))
dist.put("0,0", 0)
while (pq.isNotEmpty()) {
val curr = pq.poll()
val x = curr[0]
val i = curr[1]
val j = curr[2]
if (i == m - 1 && j == n - 1) {
return x
}
val directions =
arrayOf(intArrayOf(i - 1, j), intArrayOf(i, j - 1), intArrayOf(i, j + 1), intArrayOf(i + 1, j))
for (dir in directions) {
val ii = dir[0]
val jj = dir[1]
if (ii in 0 until m && jj >= 0 && jj < n) {
val xx = x + 1 + 0.coerceAtLeast((grid[ii][jj] - x) / 2 * 2)
val key = "$ii,$jj"
if (!dist.containsKey(key) || dist[key]!! > xx) {
pq.offer(intArrayOf(xx, ii, jj))
dist.put(key, xx)
}
}
}
}
}
return -1
}
}