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.
Input format
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.
Output format
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.
Constraints
- 1 \u2264 r, c \u2264 500
- Each grid value is
0(open) or1(blocked).