LeetCode Entry
2812. Find the Safest Path in a Grid
Safest path in a grid with thieves
2812. Find the Safest Path in a Grid medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/603
Problem TLDR
Safest path in a grid with thieves #medium #bfs #heap
Intuition
Let’s firs build a map, marking each cell with its safety number, this can be done with Breadth-First Search from all thieves:
The path finding part is straightforward Dijkstra: choose the most optimal path from the heap, stop on the first arrival.
Approach
There are some tricks possible:
- use the grid itself as a visited set: check
0and mark with negative - we can avoid some extra work if we start safety with
1
Complexity
-
Time complexity: \(O(nmlog(nm))\)
-
Space complexity: \(O(nm)\)
Code
fun maximumSafenessFactor(grid: List<List<Int>>): Int {
val g = grid.map { it.toTypedArray() }; val n = g.size
with(ArrayDeque<Pair<Int, Int>>()) {
for (y in 0..<n) for(x in 0..<n) if (g[y][x] > 0) add(y to x)
while (size > 0) {
val (y, x) = removeFirst(); val step = g[y][x] + 1
fun a(y: Int, x: Int): Unit =
if (x in 0..<n && y in 0..<n && g[y][x] < 1) {
add(y to x); g[y][x] = step
} else Unit
a(y - 1, x); a(y, x - 1); a(y + 1, x); a(y, x + 1)
}
}
data class Path(val f: Int, val x: Int, val y: Int)
return with(PriorityQueue<Path>(compareBy { it.f })) {
add(Path(-g[0][0], 0, 0))
while (size > 0) {
val (f, x, y) = poll()
fun a(x: Int, y: Int): Unit =
if (x in 0..<n && y in 0..<n && g[y][x] > 0) {
add(Path(-min(-f, g[y][x]), x, y)); g[y][x] *= -1
} else Unit
if (x == n - 1 && y == n - 1) return -f - 1
a(x - 1, y); a(x, y - 1); a(x + 1, y); a(x, y + 1)
}; -1
}
}
pub fn maximum_safeness_factor(mut g: Vec<Vec<i32>>) -> i32 {
let (n, mut q, mut h) = (g.len(), VecDeque::new(), BinaryHeap::new());
for y in 0..n { for x in 0..n { if g[y][x] > 0 { q.push_back((y, x) )}}}
while let Some((y, x)) = q.pop_front() {
let s = g[y][x] + 1;
if y > 0 && g[y - 1][x] < 1 { q.push_back((y - 1, x)); g[y - 1][x] = s; }
if x > 0 && g[y][x - 1] < 1 { q.push_back((y, x - 1)); g[y][x - 1] = s; }
if y < n - 1 && g[y + 1][x] < 1 { q.push_back((y + 1, x)); g[y + 1][x] = s; }
if x < n - 1 && g[y][x + 1] < 1 { q.push_back((y, x + 1)); g[y][x + 1] = s; }
}
h.push((g[0][0], 0, 0));
while let Some((f, y, x)) = h.pop() {
if x == n - 1 && y == n - 1 { return f - 1 }
if y > 0 && g[y - 1][x] > 0 { h.push((f.min(g[y - 1][x]), y - 1, x)); g[y - 1][x] *= -1; }
if x > 0 && g[y][x - 1] > 0 { h.push((f.min(g[y][x - 1]), y, x - 1)); g[y][x - 1] *= -1; }
if y < n - 1 && g[y + 1][x] > 0 { h.push((f.min(g[y + 1][x]), y + 1, x)); g[y + 1][x] *= -1; }
if x < n - 1 && g[y][x + 1] > 0 { h.push((f.min(g[y][x + 1]), y, x + 1)); g[y][x + 1] *= -1; }
}; -1
}