A delivery drone flies over an R-by-C binary grid. A cell with value 0 is clear (flyable) and a cell with value 1 is blocked. The drone starts at the top-left cell (0,0) and must reach the bottom-right cell (R-1,C-1).
In one hop the drone may move to any of the up to 8 neighboring cells (horizontally, vertically, or diagonally) provided that cell is clear. The length of a path is the number of cells it visits, counting both the start and end cells.
Report the length of the shortest such path. If the start or end cell is blocked, or no clear path exists, report -1.
Input format
Line 1: two integers R and C.
Next R lines: each contains C space-separated integers, each 0 (clear) or 1 (blocked).
Output format
A single integer: the minimum path length in cells, or -1 if unreachable.
Constraints
- 1 <= R, C <= 200
- Each cell is 0 or 1.