196. Shortest Path in a Grid
A grid holds 1 for a cell you may walk on and 0 for a wall.
Find the shortest path from the top-left cell to the bottom-right cell, moving only up,
down, left or right. Print the number of CELLS on that path, counting both ends, or -1 if
there is no route.
Why a queue and not a stack: a queue finishes every cell one step away before any cell two steps away, so the FIRST time it reaches the destination is by the shortest route. A stack would find a path, but not the shortest one, which is a wrong answer, not just a slow one.
Constraints - `1 ≤ r, c ≤ 1000` - Each value is `0` or `1`.
Input
The first line contains two integers r and c.
Each of the next r lines contains c space-separated integers, each 0 or 1.
Output
Print one integer, the number of cells on the shortest path from the top-left to the bottom-right, or -1 if no path exists.
A single walkable cell counts as a path of length 1.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.