grid is an n × n grid where 0 is an open cell and 1 is a blocked one. You start on the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1). From any cell you may step to any of its 8 neighbours: up, down, left, right or one of the four diagonals, as long as that cell is open and inside the grid. A diagonal step is allowed even when the two cells beside it are blocked.
The length of a path is the number of cells on it, counting the start and the end. Write shortest_path_binary_matrix(grid: list[list[int]]) -> int that returns the length of the shortest path, or -1 if there is none (that includes a blocked start or a blocked end).
Examples:
grid = [[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 1, 0, 1, 0],
[0, 0, 1, 1, 0],
[1, 1, 1, 1, 0]]
shortest_path_binary_matrix(grid) # 11
The walls force a zigzag: down the left edge, a diagonal hop over to the middle column, up it, then diagonally over the wall at the top right and down the right edge.
shortest_path_binary_matrix([[0, 1], [1, 0]]) # 2 one diagonal step between two blocked cells
shortest_path_binary_matrix([[0, 0, 1], [0, 1, 1], [1, 1, 0]]) # -1 the corner is walled off
Constraints: 1 <= n <= 300, every cell is 0 or 1. A 1 × 1 grid holding 0 has a path of length 1.
⭐ Bonus: speed tests on 300 × 300 grids, one a long winding maze, earn a star in O(n²). Trying paths one by one blows up long before that size.
Show hint
every step costs the same, so the first time a breadth-first search reaches a cell, it has found the shortest way there.