Minimum Time to Visit a Cell In a Grid
Problem
You get an m × n matrix grid of non-negative integers, where grid[r][c] is the earliest second at which you are allowed to step into cell (r, c). You start in the top-left cell at second 0, every move to an edge-adjacent cell takes exactly 1 second, and you may revisit cells — but you can never stand still. Return the minimum second at which you can reach the bottom-right cell, or −1 if it is impossible.
Since waiting in place is forbidden, the only way to kill time is to bounce between two adjacent cells, and each round trip costs exactly 2 seconds — so the parity of your arrival times is locked in.
grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]7import heapq
def minimum_time(grid):
if grid[0][1] > 1 and grid[1][0] > 1:
return -1 # locked in at the start
m, n = len(grid), len(grid[0])
dist = [[float("inf")] * n for _ in range(m)]
seen = [[False] * n for _ in range(m)]
dist[0][0] = 0
pq = [(0, 0, 0)] # (time, row, col)
while pq:
t, r, c = heapq.heappop(pq)
if seen[r][c]:
continue
seen[r][c] = True
if r == m - 1 and c == n - 1:
return t
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if not (0 <= nr < m and 0 <= nc < n) or seen[nr][nc]:
continue
nt = t + 1
if nt < grid[nr][nc]: # too early: bounce to wait
nt = grid[nr][nc] + (grid[nr][nc] - nt) % 2
if nt < dist[nr][nc]:
dist[nr][nc] = nt
heapq.heappush(pq, (nt, nr, nc))
return -1function minimumTime(grid) {
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
const m = grid.length, n = grid[0].length;
const dist = Array.from({ length: m }, () => Array(n).fill(Infinity));
const seen = Array.from({ length: m }, () => Array(n).fill(false));
dist[0][0] = 0;
const pq = [[0, 0, 0]]; // [time, row, col]
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]); // smallest time first
const [t, r, c] = pq.shift();
if (seen[r][c]) continue;
seen[r][c] = true;
if (r === m - 1 && c === n - 1) return t;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
let nt = t + 1;
if (nt < grid[nr][nc]) nt = grid[nr][nc] + ((grid[nr][nc] - nt) % 2);
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push([nt, nr, nc]);
}
}
}
return -1;
}int minimumTime(int[][] grid) {
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int m = grid.length, n = grid[0].length;
int[][] dist = new int[m][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
boolean[][] seen = new boolean[m][n];
dist[0][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.add(new int[]{0, 0, 0}); // {time, row, col}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int t = cur[0], r = cur[1], c = cur[2];
if (seen[r][c]) continue;
seen[r][c] = true;
if (r == m - 1 && c == n - 1) return t;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
int nt = t + 1;
if (nt < grid[nr][nc]) nt = grid[nr][nc] + (grid[nr][nc] - nt) % 2;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.add(new int[]{nt, nr, nc});
}
}
}
return -1;
}int minimumTime(vector<vector<int>>& grid) {
if (grid[0][1] > 1 && grid[1][0] > 1) return -1;
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
vector<vector<bool>> seen(m, vector<bool>(n, false));
dist[0][0] = 0;
priority_queue<array<int,3>, vector<array<int,3>>, greater<>> pq;
pq.push({0, 0, 0}); // {time, row, col}
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!pq.empty()) {
auto [t, r, c] = pq.top(); pq.pop();
if (seen[r][c]) continue;
seen[r][c] = true;
if (r == m - 1 && c == n - 1) return t;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) continue;
int nt = t + 1;
if (nt < grid[nr][nc]) nt = grid[nr][nc] + (grid[nr][nc] - nt) % 2;
if (nt < dist[nr][nc]) {
dist[nr][nc] = nt;
pq.push({nt, nr, nc});
}
}
}
return -1;
}Explanation
At first glance this looks like BFS, but the cost of entering a neighbour is not constant: a cell with threshold grid[nr][nc] may force you to kill time before stepping in. The earliest arrival at a cell depends only on when you leave the previous one, and arrival times never decrease along a path, so Dijkstra applies: always settle the cell with the smallest tentative arrival time.
The waiting trick is the heart of the problem. You cannot stand still, but you can step to any visited neighbour and come straight back — one bounce costs exactly 2 seconds. So if you stand somewhere at time t, you can also stand there at t+2, t+4, …: the parity of your position is locked. Arriving at a neighbour therefore happens at some time ≥ t+1 with the same parity as t+1. The earliest legal entry is grid[nr][nc] itself when the parities match, otherwise one second later — exactly nt = g + ((g − (t+1)) % 2).
One special case has no bounce partner: at second 1 you are forced to move into (0,1) or (1,0). If both demand a time greater than 1 you can never make your first move, so the answer is −1 immediately — that is the up-front check before the heap loop.
On the default grid the heap settles cells in arrival order 0, 1, 2, 3, 3, 4, 4, 5, 5, 6, 7. The interesting pop is (1,2) at t = 3: its neighbour (1,3) needs t ≥ 5, but arriving at 5 would need odd parity while we arrive on even ticks, so the bounce-wait pushes it at 6. The target (2,3) is finally popped at t = 7, which is the answer.
Each cell is settled at most once (the seen check discards stale heap entries), and each of the O(m·n) edges is relaxed a constant number of times with heap operations costing O(log(m·n)). That gives O(m·n log(m·n)) time and O(m·n) space for dist, seen and the heap.