Problem Description

Bitaro, who loves fashion, has bought a new carpet. The carpet is a rectangle divided into a grid of $H$ rows and $W$ columns, with each cell painted either white or black. The color of the cell at the $i$-th row from the top and the $j$-th column from the left ($1 \leq i \leq H$, $1 \leq j \leq W$) is determined by the $j$-th character of the string $S_i$, where . represents white and # represents black.

Bitaro has placed a piece on the top-left cell of the carpet and came up with a game where he moves the piece to the bottom-right cell by performing the following operation any number of times:

• Move the piece to a cell that is adjacent to the current cell (up, down, left, or right) and has a different color.

Bitaro wants to minimize the number of operations to reach the bottom-right cell. However, depending on the pattern of the carpet, it might not be possible to reach the destination.

Given the pattern of the carpet, write a program to determine if it is possible to move the piece from the top-left cell to the bottom-right cell by repeating the operations. If possible, find the minimum number of operations required. If not, output -1.

Input Format

The input is given from the standard input in the following format:

$H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$

Output Format

If it is possible to move the piece from the top-left cell to the bottom-right cell by repeating the operations, output the minimum number of operations. If not, output -1.

Sample Input and Output

Sample Input #1

4 5
...#.
#####
...#.
#.###

Sample Output #1

9

Sample Input #2

3 3
...
...
...

Sample Output #2

-1

Sample Input #3

1 5
.#.#.

Sample Output #3

4

Sample Input #4

5 5
###.#
.#...
.#..#
.####
##..#

Sample Output #4

12

Sample Input #5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

Sample Output #5

12

Notes/Hints

Constraints

• $1 \leq H \leq 500$.
• $1 \leq W \leq 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ is a string of length $W$ ($1 \leq i \leq H$).
• Each character in $S_i$ is either . or # ($1 \leq i \leq H$).
• $H$ and $W$ are integers.

Subtasks

1. ($4$ points) $H = 1$.
2. ($14$ points) $H \leq 5$, $W \leq 5$.
3. ($24$ points) $H \leq 30$, $W \leq 30$.
4. ($58$ points) No additional constraints.

Grading Notes

All submissions are graded on the judge system.

A submitted source code is considered correct for a subtask if it returns the correct result for all test inputs corresponding to that subtask.

The score for each submission is the sum of the points for the subtasks that the submitted source code is considered correct for.

The score for this task is the maximum score of all submissions for this task.

The current score can be checked under "My Score Status" on the "Submission Results" tab.

见题面 Input 部分

见题面 Output 部分