Shortest 8-Directional Clear Path Across a Binary Grid

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

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

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

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

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.

Shortest Corner-Connected Clear Path in a Binary Grid

Hints

1. Settle the cases the rules fix directly first: a blocked start or end cell, and the single-cell grid.
2. A diagonal step only needs the two cells it connects to be open; the cells beside the step do not matter.
3. The length counts cells, not moves, so a path made of k moves has length k + 1.

Approach

Treat every open cell as a node joined to each open cell among its up to eight neighbours, and run a breadth-first search from (0, 0). Every move adds exactly one cell to the path, so the search discovers cells in non-decreasing order of path length. The start is recorded with length 1, and each newly discovered cell gets its parent's length plus 1. Invariant: when a cell is first discovered, its recorded length is the minimum number of cells on any clear path to it, because every cell with a smaller length was dequeued earlier. So the first time (n - 1, n - 1) is discovered its length can be returned immediately; if the queue empties without discovering it, the corner is unreachable and the answer is -1. A diagonal move checks only its target cell, so a corner-touch move between two blocked side cells is allowed, as the rules require. Edge cases: a blocked start or end returns -1 before searching, which also covers n = 1 with the single cell blocked; n = 1 with an open cell returns 1 because the path is that one cell. Each cell is enqueued at most once and examines eight neighbours, so the work is O(n^2) time with O(n^2) space for the length table and queue. The answer is at most n * n = 250,000, so a 32-bit int suffices in every language.

• Time complexity: O(n^2)
• Space complexity: O(n^2)