Park Navigation: Find the Shortest Path Through a Park Map Avoiding Restricted Zones

Question

## Problem

A park is represented as an `m x n` grid. Cells are `0` (open path), `1` (obstacle), or `2` (rest area -- costs double movement). Find the shortest-time path from the entrance `(0,0)` to the exit `(m-1,n-1)`. Moving to an adjacent cell costs 1 time unit, except rest areas which cost 2.

```python
def park_navigate(grid: list[list[int]]) -> int:
    # Returns minimum time, or -1 if no path exists
    pass
```

**Example:**
```
grid = [
  [0, 0, 1],
  [0, 2, 0],
  [0, 0, 0],
]
Shortest path (0,0)->(1,0)->(2,0)->(2,1)->(2,2) = 4
output -> 4
```

## Approach

Dijkstra with a min-heap, since edge costs are non-uniform (1 or 2). BFS alone is insufficient. O(m*n log(m*n)).

## Follow-ups
1. Why can't you use standard BFS here? What property of BFS does the rest-area cost violate?
2. If costs are only 1 or 2, you can use 0-1 BFS (deque). Explain how.
3. The park is updated frequently (obstacles change). How do you avoid full re-computation?
4. Find the path that minimizes the number of rest areas visited, regardless of time.

Park Navigation: Find the Shortest Path Through a Park Map Avoiding Restricted Zones

Question Details

Full Details

Topics

More from Square/Block