Shortest Escape Route in Binary Obstacle Grid
Problem Description
You are given an `n x n` binary matrix `terrain` where `0` represents a passable cell and `1` represents a blocked cell.
Find the length of the shortest path from the top-left cell `(0, 0)` to the bottom-right cell `(n-1, n-1)`. You may move in any of the **8 directions** (horizontally, vertically, or diagonally) to an adjacent passable cell.
Return the length of the shortest path (measured in number of cells visited, including start and end), or `-1` if no such path exists.
**Example 1:**
```
Input: terrain = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
```
**Example 2:**
```
Input: terrain = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
```
Constraints
- 1 <= n <= 100
- terrain[i][j] is either 0 or 1
Follow-up
Extend this to a weighted grid where each passable cell has a traversal cost; find the minimum-cost path.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first ā submit an accepted solution.