Shortest Path in a Labyrinth

You are given a labyrinth represented as a grid of size \(M \times N\). Each cell is either 0 (open) or 1 (wall). Your task is to find the shortest path from the top-left corner \((0,0)\) to the bottom-right corner \((M-1, N-1)\) by moving up, down, left, or right. If no valid path exists, output \(-1\). The number of steps is counted as the number of cells visited along the path including the start and the destination.

Note: Movement is allowed only in the four cardinal directions (up, down, left, right) and you cannot pass through walls.

Constraints:

• \(1 \le M, N \le 10^3\) (depending on the input, but typical test cases are small)
• Each cell is either 0 or 1.

The problem is guaranteed to have at least one test case where the labyrinth is non-empty.

inputFormat

The first line contains two integers \(M\) and \(N\) --- the number of rows and columns respectively.

The following \(M\) lines each contain \(N\) space-separated integers (each either 0 or 1) representing the labyrinth.

Input is given through stdin.

outputFormat

Output a single integer --- the minimum number of steps required to reach the destination \((M-1, N-1)\) from the start \((0,0)\). If it is not possible to reach the destination, output \(-1\).

Output should be printed to stdout.

## sample

5 6
0 1 0 0 0 0
0 1 1 1 1 0
0 0 0 0 0 0
1 0 1 1 1 1
0 0 0 0 0 0

10