Minimum Steps in Grid with Obstacles

You are given a grid of size \(N \times M\) where each cell is either free (0) or blocked (1). Your task is to determine the minimum number of steps required to move from the top-left corner (position \((0,0)\)) to the bottom-right corner (position \((N-1, M-1)\)). You can move up, down, left, or right. If the destination cannot be reached or the starting/ending cell is blocked, print \(-1\).

Note: The number of steps is defined as the number of moves between cells. For example, moving from one cell to an adjacent cell is counted as 1 step.

inputFormat

The first line of input contains two integers \(N\) and \(M\) separated by a space.

The following \(N\) lines each contain \(M\) integers (either 0 or 1) separated by spaces representing the grid.

You should read input from stdin.

outputFormat

Output a single line containing the minimum number of steps to reach the destination (bottom-right corner), or \(-1\) if it is not possible.

Write your answer to stdout.

5 5
0 0 0 0 0
1 1 0 1 0
0 0 1 0 0
0 1 0 1 0
0 0 0 0 0

8