Shortest Clear Route Through a Blocked Board
Implement shortestClearPath
You are given a square-or-rectangular board where 0 is an open cell and 1 is a blocked cell. Find the shortest route from the top-left cell to the bottom-right cell that only visits open cells, where each move goes to any of the 8 surrounding cells. Return the number of cells on that route (both ends counted), or -1 when no route exists.
Because every move costs the same, a breadth-first search over the cells finds the answer in one pass.
Example 1:
Input: grid = [[0,0,1,0],[1,0,1,0],[1,1,0,0],[0,1,1,0]]
Output: 4
Example 2:
Input: grid = [[0,1,1],[1,0,1],[1,1,0]]
Output: 3
Example 3:
Input: grid = [[0,1],[1,1]]
Output: -1
+ 12 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ rows, cols ≤ 12; grid[r][c] is 0 (open) or 1 (blocked) - ●
A route starts at the top-left cell and ends at the bottom-right cell, visiting only open cells - ●
You may step to any of the 8 surrounding cells (sides and corners) - ●
Return the number of cells on the shortest route (including both ends), or -1 if there is none
grid =
[[0,0,1,0], [1,0,1,0], [1,1,0,0], [0,1,1,0]]