Shortest Path in a Grid

Given a 2D grid of dimensions M×N, where each cell is either empty (denoted by 0) or blocked (denoted by 1), your task is to find the shortest path from the top-left corner to the bottom-right corner. You may move up, down, left, or right.

If the grid is represented as a matrix \(G\), you need to find the minimum number of moves \(d\) such that starting from \(G[0][0]\) you reach \(G[M-1][N-1]\). The relation can be written as:

\( path_{length} = d \)

If no path exists, output \(-1\).

inputFormat

The input is given from stdin in the following format:

M N
row1_element1 row1_element2 ... row1_elementN
... 
rowM_element1 rowM_element2 ... rowM_elementN

Where the first line contains two integers \(M\) and \(N\) representing the number of rows and columns respectively. Each of the following \(M\) lines contains \(N\) integers (0 or 1) separated by spaces.

outputFormat

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

3 3
0 0 0
1 1 0
0 0 0

4