Shortest Path in a Grid

You are given a grid of dimensions \(n \times m\) consisting of 0s and 1s, where 0 represents an open cell and 1 represents a blocked cell. 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 \((n-1, m-1)\)). You can only move in the four cardinal directions (up, down, left, right), and you cannot move into a blocked cell.

If either the start or the destination is blocked, or if there is no valid path, output \(-1\). For a valid path, count the starting cell as a step. For example, in a grid with only one cell and that cell is open, the answer is 1.

inputFormat

The input is read from standard input. 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 next \(n\) lines each contain \(m\) space-separated integers (either 0 or 1) which represent the grid.

outputFormat

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

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 1 0
0 1 1 1 0
0 0 0 0 0

9