Shortest Path with a Single Obstacle Break

You are given a grid with n rows and m columns where each cell is either 0 or 1. The cell with 0 is a free space, and the cell with 1 is an obstacle. Your task is to find the shortest path from the top-left corner (0,0) to the bottom-right corner (n-1, m-1) by moving up, down, left, or right.

You are allowed to break through at most one obstacle (i.e. convert a single 1 to 0) along your path. If even after breaking one obstacle the destination is unreachable, output -1.

The shortest path is measured as the number of moves made. For example, if you start at (0,0) and move right to (0,1), that is considered one step.

The problem can be stated mathematically as follows:

$$\text{Find minimum } d \text{ such that there is a path } P : (0,0) \rightarrow (n-1, m-1) \text{ with at most one obstacle break.} $$

inputFormat

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

1. The first line contains two integers n and m, representing the number of rows and columns.
2. The next n lines each contain m space-separated integers (either 0 or 1) representing the grid.

outputFormat

Output a single integer to standard output (stdout): the minimum number of moves required to reach the destination. If there is no valid path, output -1.

## sample

3 3
0 0 0
0 0 0
0 0 0

4