Shortest clear path in a grid
A square grid grid has n rows and n columns. A cell holding 0 is open and a cell holding 1 is blocked. You start on the top-left cell and want to reach the bottom-right cell, stepping only on open cells. From a cell you may step to any of its 8 neighbors: up, down, left, right, or one of the four diagonals.
Return the number of cells on the shortest such path, counting the first and the last cell. Return -1 when there is no path, which includes the case where the start or the end cell is blocked. A 1 × 1 open grid is a path of one cell, so its answer is 1. You may change grid while you work.
Cells are written (row, column), counting from 0.
grid = [[0, 1, 0], [0, 1, 0], [0, 0, 0]]Output4Down to (1, 0), diagonally to (2, 1), then right to (2, 2). A path of 3 cells would need the center cell, which is blocked.
grid = [[0, 0, 1], [1, 1, 1], [0, 0, 0]]Output-1The middle row is blocked all the way across, and a diagonal step still has to land on an open cell.
grid = [[1, 0], [0, 0]]Output-1The start cell is blocked.
1 ≤ n ≤ 100
Every cell is 0 or 1.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.