Minimal Steps with an Additional Obstacle

You are given a grid with n rows and m columns, where each cell is either free (represented by 0) or blocked (represented by 1). A robot starts at the top-left corner (cell (0,0)) and aims to reach the bottom-right corner (cell (n-1, m-1)).

The robot has a unique ability: it can place one additional obstacle (i.e. change a free cell to blocked) anywhere in the grid, and it may choose not to place any if unnecessary. After optionally placing an obstacle, the robot will move using only up, down, left, and right moves. Determine the minimum number of steps required to go from the start to the destination. If there is no valid path, output -1.

Note: The placement of an obstacle might sometimes force a shorter path if the original free grid causes the robot to take a detour.

The answer should be computed using the following approach: first, calculate the shortest path in the original grid. Then, for each free cell, temporarily convert it into an obstacle and recompute the shortest path. The final answer is the minimum achievable number of steps among all these configurations. If no configuration allows for a path, output -1.

inputFormat

The input is given via standard input (stdin) and is formatted as follows:

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

For example, a grid of 3 rows and 3 columns might be provided as:

3 3
0 0 0
0 1 0
0 0 0

outputFormat

Output the minimum number of steps required to reach the bottom-right corner from the top-left corner after optionally placing one additional obstacle. If it is not possible to reach the destination, output -1.

The output should be sent to standard output (stdout).

## sample

3 3
0 0 0
0 1 0
0 0 0

4