Minimum Moves in a Grid

You are given a grid with obstacles, represented by 1, and free cells, represented by 0. Your task is to determine the minimum number of moves required to travel from the top-left corner (0, 0) to the bottom-right corner (N-1, M-1). You can move one step at a time in the four cardinal directions: up, down, left, and right. If the starting cell or the destination cell is blocked or if there is no valid path, then output -1.

The optimal solution requires the use of a breadth-first search (BFS) algorithm to calculate the shortest path in an unweighted grid.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of rows and columns in the grid respectively.
The following \(N\) lines each contain \(M\) space-separated integers (either 0 or 1) representing the grid. A value of 0 indicates a free cell, whereas 1 indicates an obstacle.

outputFormat

Output a single integer, which is the minimum number of moves required to reach the bottom-right cell from the top-left cell. If it is impossible to reach the destination, output -1.

3 3
0 0 0
1 1 0
0 0 0

4