LeetCode Entry
2577. Minimum Time to Visit a Cell In a Grid
Min time start-end 4-d travel in 2D matrix with waiting
2577. Minimum Time to Visit a Cell In a Grid hard
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/815
Problem TLDR
Min time start-end 4-d travel in 2D matrix with waiting #hard #dijkstra
Intuition
Start with simple BFS.
We can wait by moving back and forward incrementing time by 2.
If we put k
Approach
- we can use a simple boolean visited set instead of comparing the time, as we always reach the earliest time first
Complexity
-
Time complexity: \((nmlog(nm))\)
-
Space complexity: \(mn\)
Code
fun minimumTime(grid: Array<IntArray>): Int {
if (grid[0][1] > 1 && grid[1][0] > 1) return -1
val q = PriorityQueue<List<Int>>(compareBy { it[2] }); q += listOf(0, 0, 0)
val visited = Array(grid.size) { BooleanArray(grid[0].size)}
while (q.size > 0) {
val (y, x, t) = q.poll()
if (y == grid.size - 1 && x == grid[0].size - 1) return t
if (visited[y][x]) continue; visited[y][x] = true
for ((y1, x1) in listOf(y - 1 to x, y to x + 1, y + 1 to x, y to x - 1))
if (y1 in grid.indices && x1 in grid[0].indices && !visited[y1][x1])
q += listOf(y1, x1, 1 + max(grid[y1][x1] - max(0, grid[y1][x1] - t) % 2, t))
}; return -1
}
pub fn minimum_time(grid: Vec<Vec<i32>>) -> i32 {
if grid[0][1] > 1 && grid[1][0] > 1 { return -1 }
let mut h = BinaryHeap::from_iter([(0, 1, 1)]);
let mut time = vec![vec![i32::MAX; grid[0].len()]; grid.len()];
while let Some((t, y, x)) = h.pop() {
for (y1, x1) in [(y - 1, x), (y + 1, x), (y, x - 1), (y, x + 1)] {
if y1.min(x1) < 1 || y1 > grid.len() || x1 > grid[0].len() { continue }
let t = (-t + 1).max(grid[y1 - 1][x1 - 1] + (grid[y1 - 1][x1 - 1] + t + 1) % 2);
if t < time[y1 - 1][x1 - 1] { time[y1 - 1][x1 - 1] = t; h.push((-t, y1, x1)); }
}
}; time[grid.len() - 1][grid[0].len() - 1]
}
int minimumTime(vector<vector<int>>& g) {
if (min(g[0][1], g[1][0]) > 1) return -1;
priority_queue<array<int, 3>> pq; pq.push({0, 0, 0});
vector<vector<int>> time(g.size(), vector<int>(g[0].size(), INT_MAX));
while (pq.size()) {
auto [t, y, x] = pq.top(); pq.pop();
for (auto [y1, x1] : array<int[2],4>..{y - 1, x}, {y + 1, x}, {y, x - 1}, {y, x + 1\}..) { // replace '.' to '{'
if (min(y1, x1) < 0 || y1 >= g.size() || x1 >= g[0].size()) continue;
int t1 = max(-t + 1, g[y1][x1] + (g[y1][x1] + t + 1) % 2);
if (t1 >= time[y1][x1]) continue;
time[y1][x1] = t1; pq.push({-t1, y1, x1});
}
} return time.back().back();
}