Shortest Path in a Grid

Given an n × m grid where each cell is either open (represented by 0) or blocked by an obstacle (represented by 1), your task is to compute the length of the shortest path from the top-left corner (cell at coordinates (0, 0)) to the bottom-right corner (cell at coordinates (n-1, m-1)). You are allowed to move in four directions: up, down, left, and right. If there exists no valid path, output -1.

The grid is provided as input from stdin with the following format:

• The first line contains two integers n and m, separated by a space.
• The next n lines each contain m integers (0 or 1) separated by spaces.

The length of the path is defined as the number of cells traversed, including both the start and end cells. Mathematically, if a valid path exists with length \(L\), then the value \(L\) is the answer, otherwise, the answer is \(-1\).

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 1000) representing the number of rows and columns in the grid. Following this, there are n lines each containing m integers separated by spaces, where each integer is either 0 (open cell) or 1 (obstacle).

outputFormat

Output 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
0 0 0
0 0 0

5