Shortest Path in a Grid

You are given an m x n grid where each cell contains either a 0 (free) or a 1 (obstacle). Your task is to determine the shortest path from the top-left corner (cell (0,0)) to the bottom-right corner (cell (m-1,n-1)). You can move in the four cardinal directions: up, down, left, and right. The length of the path is defined as the number of moves taken. If either the starting or ending cell is an obstacle or no valid path exists between them, output -1.

This problem can be solved using a Breadth-First Search (BFS) algorithm. The time complexity of the solution is \(O(m \times n)\) and it works within the problem constraints.

inputFormat

The input is given via stdin and is formatted as follows:

 m n
 row1_element1 row1_element2 ... row1_elementn
 row2_element1 row2_element2 ... row2_elementn
 ...
 rowm_element1 rowm_element2 ... rowm_elementn

Here, m and n are integers representing the number of rows and columns respectively. Each of the next m lines contains n integers (each either 0 or 1), representing one row of the grid.

outputFormat

Output a single integer to stdout: the length of the shortest path from the top-left corner to the bottom-right corner. If a valid path does not exist, output -1.

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

6