Minimum Moves to Reach Target

You are given an n by m grid representing a maze. Each cell is either an empty cell denoted by . or a wall denoted by #. Your task is to determine the minimum number of moves required to go from the starting cell at \((1,1)\) to the target cell at \((n,m)\).

You are allowed to remove at most one wall during your journey. A move is defined as moving from one cell to one of its four adjacent cells (up, down, left, or right). If it is impossible to reach the target even after removing one wall, output -1.

Note: The grid is 1-indexed in the description, but the input is given row by row starting from the first row.

inputFormat

The first line contains two integers n and m, representing the number of rows and columns of the grid, respectively. The next n lines each contain m characters separated by spaces. Each character is either . (empty cell) or # (wall).

outputFormat

Output a single integer: the minimum number of moves required to reach the target cell. If the target cannot be reached even after removing one wall, output -1.

## sample

5 6
. . . # . .
. # . # . #
. # . . . .
. # # # . #
. . . . . .

9

</p>