Minimum Moves in a Grid

You are given a grid of dimensions \(N \times M\), where each cell is either free (denoted by 1) or blocked (denoted by 0). The task is to find the minimum number of moves required to travel from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((N-1,M-1)\)). You can move in one of the four directions: up, down, left, or right.

The number of moves is counted by the number of steps taken (each step moves to an adjacent cell). If either the starting cell or the destination cell is blocked, or if there is no valid path between them, output \(-1\).

Note: A move is valid only if it stays within the grid boundaries and the destination cell is free (has a value of 1).

inputFormat

The input is given via standard input (stdin). The first line contains two integers \(N\) and \(M\) separated by a space, representing the number of rows and columns of the grid respectively. The following \(N\) lines each contain \(M\) integers (each integer is either 0 or 1) separated by spaces, representing the grid.

For example:

3 3
1 1 0
0 1 0
0 1 1

outputFormat

Output a single integer via standard output (stdout): the minimum number of moves required to reach the bottom-right corner from the top-left corner. If it is impossible to reach the destination, output \(-1\).

3 3
1 1 0
0 1 0
0 1 1

4