AceYourInterviews
Checking sign-in…

101. Shortest Path in a Binary Matrix

CoreEight-neighbor BFS with path length measured in cells

Travel from the top-left cell to the bottom-right cell through open cells. You may move to any of the eight neighboring positions, including diagonals.

Count cells on the path, including both endpoints, rather than counting only moves. A blocked endpoint or an unreachable destination produces the documented failure result.

Example 1

Input

[[0,1,0],[0,0,0],[1,1,0]]

Output

3

Explanation: The diagonal route (0,0)→(1,1)→(2,2) contains three cells.

Example 2

Input

[[0,1],[1,0]]

Output

2

Explanation: The diagonal is permitted despite the blocked orthogonal neighbors.

Example 3

Input

[[0]]

Output

1

Explanation: The path contains its one open endpoint cell.

Constraints

  • 0 <= n
  • n * n <= 105
  • grid.length == grid[r].length == n
  • Cells are 0 (open) or 1 (blocked).
Hints
Hint 1

Model open cells as a unit-weight graph.

Hint 2

There are eight possible moves, and start distance is one cell.

Hint 3

BFS with a separate discovery-distance matrix; stop at the first target pop.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

Eight-direction shortest route counts cells

[[0,1,0],[0,0,0],[1,1,0]]
3