You are given a grid of r rows and c columns. Each cell is either open (0) or blocked (1). From an open cell you may step to an adjacent open cell in one of four directions: up, down, left, or right. You start on the top-left cell (0, 0) and want to reach the bottom-right cell (r-1, c-1).
Print the length of a shortest walk, measured as the number of cells visited including both the start and the destination. For example, a walk that only visits the single start cell (when it is also the destination) has length 1.
If the start or destination cell is blocked, or the destination cannot be reached, print -1.
Line 1: two integers r and c.
Next r lines: each contains c integers (each 0 or 1) separated by spaces \u2014 the grid rows in order.
A single integer: the number of cells on a shortest walk from (0,0) to (r-1,c-1), or -1 if no such walk exists.
0 (open) or 1 (blocked).Detour around a wall
Input
3 3 0 0 0 1 1 0 0 0 0
Expected
5
Explanation
The middle row is walled except its last column, so a shortest walk is (0,0)\u2192(0,1)\u2192(0,2)\u2192(1,2)\u2192(2,2), visiting 5 cells.
Blocked corner
Input
2 2 0 1 1 0
Expected
-1
Explanation
The destination (1,1) is open but every route is blocked by the two 1-cells; there is no walk, so the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →