Shortest Path in a Grid with Obstacles

You are given a 2D grid consisting of 0s and 1s, where 0s represent empty cells and 1s represent obstacles. Your task is to find the shortest path from the top-left cell (0, 0) to the bottom-right cell (n-1, m-1) by moving in the four cardinal directions (up, down, left, right).

The length of the path is defined as the number of cells visited (including both the starting and ending cells). If there is no valid path, output -1.

The problem can be mathematically interpreted as follows: Given a grid of size \( n \times m \), find the minimum \( d \) such that there exists a sequence of cells \( (r_0, c_0), (r_1, c_1), \dots, (r_d, c_d) \) satisfying:

• \( (r_0, c_0) = (0, 0) \) and \( (r_d, c_d) = (n-1, m-1) \),
• For all \( 0 \leq i < d \), \( |r_{i+1} - r_i| + |c_{i+1} - c_i| = 1 \),
• Each cell \( (r_i, c_i) \) is not an obstacle (i.e. its value is 0).

If no such path exists then the answer is \( -1 \). The expected time complexity is \( O(n \times m) \) since each cell is visited at most once.

inputFormat

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

n m
row1
row2
...
rown

Where:

• n and m are non-negative integers representing the number of rows and columns respectively. Note: If either n or m is zero, the grid is considered empty.
• Each of the next n lines contains m integers (either 0 or 1) separated by spaces, representing one row of the grid.

outputFormat

The output should be written to stdout and must be a single integer representing the length of the shortest path from the top-left cell to the bottom-right cell. Output -1 if no such path exists.

## sample

0 0

-1