카펫

문제

멋내기를 좋아하는 비타로는 카펫을 새로 장만했다. 카펫은 세로 $H$ 행, 가로 $W$ 열의 격자 모양으로 나누어진 직사각형 모양을 하고 있으며, 각 칸은 흰색과 검은색 중 하나의 색으로 칠해져 있다. 카펫의 위에서 $i$ 번째 행, 왼쪽에서 $j$ 번째 열 ($1 \le i \le H$, $1 \le j \le W$) 에 있는 칸의 색은, 문자열 $S_{i}$ 의 $j$ 번째 문자가 . 일 때 흰색, # 일 때 검은색이다.

비타로는, 카펫의 가장 왼쪽 위 칸에 말을 놓고, 다음 조작을 몇 번 수행하여, 그 말을 카펫의 가장 오른쪽 아래 칸에 도달시키는 놀이를 떠올렸다.

• 말이 놓여 있는 칸과 색이 다르고, 상하좌우로 인접한 칸을 $1$ 개 골라, 그 칸으로 말을 이동시킨다.

비타로는, 도달할 때까지의 조작 횟수를 가능한 한 적게 하고 싶다. 다만, 카펫의 무늬에 따라서는 도달시킬 수 없을지도 모른다.

카펫의 무늬 정보가 주어졌을 때, 조작을 반복하여 왼쪽 위 칸에서 오른쪽 아래 칸으로 말을 도달시키는 것이 가능한지 판정하고, 가능하면 조작 횟수의 최솟값을 구하는 프로그램을 작성하시오.

제한

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_{i}$ 는 길이 $W$ 의 문자열이다 ($1 \le i \le H$).
• $S_{i}$ 의 각 문자는 . 또는 # 이다 ($1 \le i \le H$).
• $H, W$ 는 정수이다.

서브태스크

1. ($4$ 점) $H = 1$.
2. ($14$ 점) $H \le 5$, $W \le 5$.
3. ($24$ 점) $H \le 30$, $W \le 30$.
4. ($58$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$H$ $W$
$S_{1}$
$S_{2}$
$:$
$S_{H}$

출력

조작을 반복하여 왼쪽 위 칸에서 오른쪽 아래 칸으로 말을 도달시키는 것이 가능한 경우에는 조작 횟수의 최솟값을, 불가능한 경우에는 -1 을, 표준 출력에 $1$ 줄로 출력한다.

채점 관련 주의사항

모든 제출은 채점 시스템에서 채점된다.

제출된 소스 코드는, 서브태스크에 대응하는 모든 채점용 입력 데이터에 대해 올바른 결과를 반환했을 때, 그 서브태스크에 대해 정답으로 인정된다.

각 제출의 점수는, 제출된 소스 코드에 대해 정답으로 인정된 서브태스크의 점수의 합이다.

이 과제의 점수는, 이 과제에 대한 모든 제출의 점수의 최댓값이다.

현재 점수는 「제출 결과」 탭의 「나의 점수 현황」에서 확인할 수 있다.

예제 입력 1

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

예제 출력 1

9

예를 들어, 그림과 같은 조작을 생각할 수 있다.

왼쪽 예에서는 $9$ 번의 조작으로, 오른쪽 예에서는 $13$ 번의 조작으로, 왼쪽 위 칸에서 오른쪽 아래 칸으로 말을 도달시키는 것이 가능하다.

$9$ 번보다 적은 조작 횟수로 도달시키는 것은 불가능하므로, $9$ 를 출력한다.

이 예제는 서브태스크 $2, 3, 4$ 의 제약을 만족한다.

예제 입력 2

3 3
...
...
...

예제 출력 2

-1

처음부터 조작을 할 수 없는 경우도 있다. 이 경우, 말을 오른쪽 아래 칸에 도달시키는 것은 불가능하므로, -1 을 출력한다.

이 예제는 서브태스크 $2, 3, 4$ 의 제약을 만족한다.

예제 입력 3

1 5
.#.#.

예제 출력 3

4

이 예제는 모든 서브태스크의 제약을 만족한다.

예제 입력 4

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

예제 출력 4

12

이 예제는 서브태스크 $2, 3, 4$ 의 제약을 만족한다.

예제 입력 5

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

예제 출력 5

12

이 예제는 서브태스크 $3, 4$ 의 제약을 만족한다.