Shortest Path in a Grid with Obstacles

You are given a 2D grid of integers of size \(N \times M\). Each cell contains either a 0 or a 1. A cell containing 0 is walkable, while a cell containing 1 is an obstacle. You can move in four directions: up, down, left, and right.

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)\)). The path length is defined as the number of cells visited including the start and end cells. If either the start or the end cell is an obstacle or if there is no valid path, output \(-1\).

More formally, if a path exists, let its length be \(L\) (the number of steps taken plus one), then output \(L\), otherwise output \(-1\).

inputFormat

The first line contains two integers \(N\) and \(M\) representing the number of rows and columns in the grid.

The following \(N\) lines each contain \(M\) integers (either 0 or 1) separated by spaces representing the grid.

Input is provided via standard input (stdin).

outputFormat

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

Output is expected on standard output (stdout).

2 2
0 0
0 0

3