#2577
Minimum Time to Visit a Cell In a Grid
expert · 1265 · lc hard +32 · verified · 56.3% accepted · 1,131 likes · top 50%
Description
You are given an m x n non-negative integer matrix grid where grid[row][col] is the earliest second you may enter cell (row, col). Starting at (0, 0) at second 0, each step to a 4-directionally adjacent cell costs 1 second. Return the minimum time to reach (m-1, n-1), or -1 if it is unreachable.
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.
Code
1
2
3