Shortest Path in a Grid

You are given an N × M grid where each cell contains either a 0 or a 1. A 0 indicates that the cell is free, while a 1 indicates an obstacle. Your task is to determine the length of the shortest path from the top-left corner to the bottom-right corner. You may only move in four directions: up, down, left, and right.

The path length is defined as the number of cells visited along the path, including both the starting cell and the destination cell. If a valid path does not exist, output -1.

Note: Either the start or the end cell might be blocked, in which case no valid path exists.

The mathematical formulation of the problem can be represented in LaTeX as follows:

\( \text{Given a matrix }A\in\{0,1\}^{N\times M}, \text{ find the minimum } k \text{ such that there exists a sequence } (i_1,j_1), (i_2,j_2), \ldots, (i_k,j_k) \) with \( (i_1,j_1) = (0,0) \) and \( (i_k,j_k) = (N-1,M-1) \), where each adjacent pair of cells is 4-connected and \( A[i_l][j_l] = 0 \) for all \( l \). If no such sequence exists, return \(-1\).

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers N and M denoting the number of rows and columns respectively.
• This is followed by N lines, each containing M space-separated integers (each either 0 or 1) representing the grid.

outputFormat

Output a single integer to stdout: the length of the shortest path from the top-left cell to the bottom-right cell. If there is no valid path, output -1.

5 6
0 1 0 0 0 1
0 1 0 1 0 0
0 0 0 1 0 0
0 1 1 1 0 1
0 0 0 0 0 0

10