Shortest Path in a Grid

You are given a grid of size \(N \times M\) composed of 0s and 1s. A 0 indicates an open cell while a 1 indicates a blocked cell. Your task is to find the shortest path from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((N-1, M-1)\)). Movement is allowed in four directions: up, down, left, and right.

If either the start or destination cell is blocked, or if there is no path between them, output \(-1\). Otherwise, output the length of the shortest path measured in the number of moves. Note that if the start and destination are the same open cell, the shortest path length is \(0\).

Input Constraints: \(1 \leq N, M \leq 1000\) (assumed for practical purposes) and the grid is provided in row-major order.

inputFormat

The first line contains two space-separated integers \(N\) and \(M\), representing the number of rows and columns in the grid respectively. The next \(N\) lines each contain \(M\) space-separated integers (either 0 or 1) denoting the grid.

Example:

3 3
0 0 0
1 1 0
1 0 0

outputFormat

Output a single integer indicating the length of the shortest path from the top-left cell to the bottom-right cell. If no such path exists, output \(-1\).

3 3
0 0 0
1 1 0
1 0 0

4