Time Limit : sec, Memory Limit : KB
English / Japanese  

Carpet

Problem Statement

Hidetaro, who loves fashion, has 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 in the i-th row from the top and the j-th column 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 #.

Hidetaro came up with a game where he places a piece on the top-left cell of the carpet and performs the following operation several times to move the piece to the bottom-right cell.

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

Hidetaro wants to minimize the number of operations required to reach the destination. However, depending on the pattern of the carpet, it may be impossible to reach the destination.

Given the information about the pattern of the carpet, write a program that determines whether it is possible to move the piece from the top-left cell to the bottom-right cell by repeating the operation, and if possible, finds the minimum number of operations required.

Constraints

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

Input

The input is given from standard input in the following format.
H W
S1
S2
:
SH

Output

If it is possible to move the piece from the top-left cell to the bottom-right cell by repeating the operation, output the minimum number of operations required. Otherwise, output -1. Output the result on a single line to standard output.

Sample Input and Output

Sample Input 1

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

Sample Output 1

9

For example, the operations shown in the figure are possible.

Illustration of two examples of operations

In the left example, it is possible to move the piece from the top-left cell to the bottom-right cell in 9 operations, and in the right example, it is possible in 13 operations.

It is impossible to reach the destination in fewer than 9 operations, so output 9.

Sample Input 2

3 3
...
...
...

Sample Output 2

-1

It may be impossible to perform any operation from the start. In this case, it is impossible to move the piece to the bottom-right cell, so output -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

Creative Commons License

Japan Information Olympiad Committee "21st Japan Information Olympiad JOI 2021/2022 Second Preliminary Round Problem"