Shortest Path in a Grid with Obstacles

You are given a grid represented by a matrix with n rows and m columns. Each cell of the matrix is either 0 or 1, where 0 represents an open space and 1 represents an obstacle.

Your task is to determine the length of the shortest path from the top-left cell (position (0,0)) to the bottom-right cell (position (n-1, m-1)). You can move up, down, left, or right from a cell, but you cannot move diagonally. If there is no valid path from the start cell to the target cell, output -1.

Note: The path length is defined as the number of cells along the path, including both the starting and ending cells. Also, note that the starting or the target cell being blocked (i.e. having a value of 1) means no valid path exists.

The shortest path problem can be solved using a breadth-first search (BFS) algorithm. In case of multiple paths, you must output the length of the shortest one.

The formula for checking the Manhattan distance between two points (i,j) and (k,l) is given by: \( |i-k| + |j-l| \), which provides a lower bound for the required path length.

inputFormat

The input is read from standard input (stdin). 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 space-separated integers (either 0 or 1), representing the grid.

outputFormat

Output a single integer to standard output (stdout) representing the length of the shortest path from the top-left corner to the bottom-right corner. If there is no valid path, output -1.## sample

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

7