Shortest 8-Directional Clear Path Across a Binary Grid
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given an `n x n` grid in which every cell is `0` (open) or `1` (blocked). Return the length of the shortest clear path from the top-left cell `(0, 0)` to the bottom-right cell `(n - 1, n - 1)`, or `-1` if no clear path exists.
A clear path is a sequence of open cells that starts at `(0, 0)` and ends at `(n - 1, n - 1)`, in which every two consecutive cells are 8-directionally adjacent: they share an edge or a corner. The length of a path is the number of cells it visits, counting both endpoints.
### Function Signature
```python
def shortest_clear_path(grid: list[list[int]]) -> int:
```
### Rules
- From cell `(r, c)` a path may move to any of the up to eight cells `(r + dr, c + dc)` with `dr` and `dc` each in `{-1, 0, 1}`, not both `0`, as long as the target cell is inside the grid and open.
- A diagonal move is allowed even when both cells that share an edge with the two cells involved are blocked; touching at a corner is enough.
- If `grid[0][0]` or `grid[n - 1][n - 1]` is `1`, return `-1`.
- If `n = 1` and the only cell is open, return `1`.
### Constraints
- `1 <= n <= 500`, where `n = len(grid)` and `len(grid[i]) == n` for every row `i`
- Every cell is `0` or `1`.
- Any answer other than `-1` is at most `n * n = 250,000`, which fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: grid = [[0, 1, 1], [1, 0, 1], [1, 1, 0]]
Output: 3
```
The path `(0, 0) -> (1, 1) -> (2, 2)` moves diagonally twice, even though every cell beside those moves is blocked.
**Example 2**
```text
Input: grid = [[0, 0, 1, 0], [1, 1, 0, 1], [1, 1, 1, 0], [1, 1, 1, 0]]
Output: 5
```
The path `(0, 0) -> (0, 1) -> (1, 2) -> (2, 3) -> (3, 3)` visits 5 cells. A 4-cell path would need three diagonal moves through `(1, 1)` and `(2, 2)`, which are blocked.
**Example 3**
```text
Input: grid = [[0, 0, 0], [1, 1, 1], [0, 0, 0]]
Output: -1
```
The middle row is entirely blocked, so no path can cross it.
Overview: Find the number of cells on the shortest path from the top-left to the bottom-right corner of a square binary grid, moving in any of eight directions through open cells only, or return -1 when no path exists. It tests modeling a grid as a graph, shortest-path reasoning and edge cases such as blocked endpoints.
You are given an `n x n` grid `grid` in which every cell is `0` (open) or `1` (blocked). Return the length of the shortest clear path from the top-left cell `(0, 0)` to the bottom-right cell `(n - 1, n - 1)`, or `-1` if no clear path exists.
A clear path is a sequence of open cells that starts at `(0, 0)` and ends at `(n - 1, n - 1)`, in which every two consecutive cells are 8-directionally adjacent: they share an edge or a corner. The length of a path is the number of cells it visits, counting both endpoints.
Rules:
- From cell `(r, c)` a path may move to any of the up to eight cells `(r + dr, c + dc)` with `dr` and `dc` each in `{-1, 0, 1}`, not both `0`, as long as the target cell is inside the grid and open.
- A diagonal move is allowed even when both cells that share an edge with the two cells involved are blocked; touching at a corner is enough.
- If `grid[0][0]` or `grid[n - 1][n - 1]` is `1`, return `-1`.
- If `n = 1` and the only cell is open, return `1`.
The result is a single integer: `-1`, or the minimum length over all clear paths. It never exceeds `n * n = 250,000`, so it always fits in a 32-bit signed integer (`int` in Java and C++).
Constraints:
- `1 <= n <= 500`, where `n = len(grid)` and `len(grid[i]) == n` for every row `i`
- Every cell is `0` or `1`.
- Any answer other than `-1` is at most `n * n = 250,000`, which fits in a 32-bit signed integer.
Example 1:
Input: grid = [[0, 1, 1], [1, 0, 1], [1, 1, 0]]
Output: 3
Explanation: The path (0, 0) -> (1, 1) -> (2, 2) moves diagonally twice, even though every cell beside those moves is blocked.
Example 2:
Input: grid = [[0, 0, 1, 0], [1, 1, 0, 1], [1, 1, 1, 0], [1, 1, 1, 0]]
Output: 5
Explanation: The path (0, 0) -> (0, 1) -> (1, 2) -> (2, 3) -> (3, 3) visits 5 cells. A 4-cell path would need three diagonal moves through (1, 1) and (2, 2), which are blocked.
Constraints
- 1 <= n <= 500, where n = len(grid) and len(grid[i]) == n for every row i
- Every cell is 0 or 1.
- Any answer other than -1 is at most n * n = 250,000, which fits in a 32-bit signed integer.
Examples
Input: ([[0]],)
Expected Output: 1
Explanation: n = 1 with the only cell open: the path is that single cell, so the length is 1 (not 0 moves).
Input: ([[1]],)
Expected Output: -1
Explanation: n = 1 with the only cell blocked: the start is blocked, so the answer is -1.
Hints
- Settle the cases the rules fix directly first: a blocked start or end cell, and the single-cell grid.
- A diagonal step only needs the two cells it connects to be open; the cells beside the step do not matter.
- The length counts cells, not moves, so a path made of k moves has length k + 1.