Carpet

Interview

Time limit2sMemory limit1024 MB

Summary

On a grid of white and black cells, move from top-left to bottom-right stepping only onto adjacent cells of the opposite color, and report the minimum number of moves or -1 if unreachable.

Level: Medium5 of 10
Topics: BFS, Graph, Shortest path, Matrix
Solved: No attempts yet

Problem

Bitaro, who likes to be stylish, bought a new carpet. The carpet is a rectangle divided into a grid of H rows and W columns, and each cell is painted either white or black. The color of the cell at row i from the top and column j from the left (1 ≦ i ≦ H, 1 ≦ j ≦ W) is white if the j-th character of the string Si is . and black if it is #.

Bitaro placed a piece on the top-left cell of the carpet and came up with a game in which he repeats the following operation any number of times to make the piece reach the bottom-right cell of the carpet.

Choose one cell that has a different color from the cell the piece is on and is adjacent to it up, down, left, or right, and move the piece to that cell.

Bitaro wants to minimize the number of operations until the piece reaches the goal. Depending on the pattern of the carpet, however, he may not be able to make it reach the goal.

Given the pattern of the carpet, write a program that determines whether the piece can be made to reach the bottom-right cell from the top-left cell by repeating the operation, and if it can, finds the minimum number of operations.

Input

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

H W
S1
S2
:
SH

Output

If the piece can be made to reach the bottom-right cell from the top-left cell by repeating the operation, print the minimum number of operations; otherwise, print -1. Print the answer on one line to standard output.

Constraints

1 ≦ H ≦ 500.
1 ≦ W ≦ 500.
(H, W) ≠ (1, 1).
Si is a string of length W (1 ≦ i ≦ H).
Each character of Si is . or # (1 ≦ i ≦ H).
H, W are integers.

Examples5

Example 1
Input
```
4 5
...#.
#####
...#.
#.###
```
Expected output
```
9
```
Example 2
Input
```
3 3
...
...
...
```
Expected output
```
-1
```
Example 3
Input
```
1 5
.#.#.
```
Expected output
```
4
```
Example 4
Input
```
5 5
###.#
.#...
.#..#
.####
##..#
```
Expected output
```
12
```

Example 5

Input

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

Expected output