Shortest Path in a Grid

You are given a 2D grid of size \(m \times n\) where each cell is either free or blocked. A free cell is represented by 0 and a blocked cell by 1. Your task is to find the length of the shortest path from the top-left corner (cell \((0,0)\)) to the bottom-right corner (cell \((m-1,n-1)\)). You may only move in the four cardinal directions: up, down, left, and right.

If the starting or ending cell is blocked, or if there is no valid path, output \(-1\).

Note: The path length is defined as the number of cells in the path including the starting and ending cells.

inputFormat

The input is given via standard input (stdin) and has the following format:

m n
row1
row2
...
rowm

Here, the first line contains two integers \(m\) and \(n\), representing the number of rows and columns in the grid respectively. Each of the following \(m\) lines contains \(n\) space-separated integers (either 0 or 1), representing the grid.

outputFormat

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

4 4
0 0 1 0
0 1 0 0
0 0 0 1
0 1 0 0

7