Find the minimum number of cells in a valid path from the top-left to the bottom-right of a binary grid, moving in 8 directions through open cells only.
Shortest Path in Binary Matrix
You are given an binary matrix grid where each cell is either 0 (open) or 1 (blocked).
A path starts at the top-left cell (0, 0) and ends at the bottom-right cell (n - 1, n - 1). From any cell, you may move to any of its 8 neighboring cells: horizontally, vertically, or diagonally adjacent.
A path is valid only if it visits open cells (0) and stays within the grid.
Return the length of the shortest valid path, measured as the number of cells visited along the path, including both the start and end cells. If no such path exists, return -1.
Notes
- If the start or end cell is blocked, the answer is immediately
-1. - The grid is square.
- The shortest path is not necessarily unique; return only the length.
Input Format
grid: a 2D integer array of sizen x ngrid[i][j]is0for an open cell or1for a blocked cell
Output Format
- Return an integer: the length of the shortest valid path from
(0, 0)to(n - 1, n - 1), or-1if unreachable
Constraints
1 <= ngridis ann x nmatrix- Cell values are binary:
0or1 - Movement is allowed in 8 directions
- The path length counts cells, not edges
Example 1
Input
grid = [[0,1],[1,0]]
Output
2
Explanation
You can move diagonally from the top-left cell to the bottom-right cell.
Example 2
Input
grid = [[0,0,0],[1,1,0],[1,1,0]]
Output
4
Explanation
One shortest path is (0,0) -> (0,1) -> (1,2) -> (2,2), which visits 4 cells.
Show 1 more example
Example 3
Input
grid = [[1,0,0],[1,1,0],[1,1,0]]
Output
-1
Explanation
The starting cell is blocked, so no valid path exists.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.