페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5855
서브태스크

카펫 (Carpet) 2초 1024MB

문제

비타로는 인테리어를 위하여 카펫을 구매했다. 카펫은 세로 H 행, 가로 W 열의 격자 모양으로 단락지어진 직사각형의 형태를 하고 있어 각 칸은 흰색 또는 검정색으로 염색 되어 있다. 카펫의 위에서 i 행째, 왼쪽에서 j 열째 ( 1 ≤ i ≤ H , 1 ≤ j ≤ W )에 있는 칸의 색은 문자열 S_i의 j 문자가 '.'이면 흰색, '#'이면 검은 색이다.

비타로는 카펫의 가장 왼쪽 상단 칸에 조각을 놓고 다음 조작을 여러 번 실시하여 그 조각을 카펫의 가장 오른쪽 아래 칸에 도달시키는 놀이를 생각했다.

  • 조각이있는 칸과 색상이 다르며 상하 좌우에 인접한 칸을 하나 선택 하고 그 칸으로 조각을 이동시킨다.

비타로는 가장 오른쪽 아래 칸에 도달하는데 필요한 조작 횟수를 가능한 한 적게 하고 싶다. 그러나 카펫의 모양에 따라 도달 할 수 없을 수도 있다.

카펫 모양의 정보가 주어지면 조작을 반복하여 왼쪽 위의 칸에서 오른쪽 하단의 칸에 조각을 도달시킬 수 있는지를 판정하고, 가능하면 조작 횟수의 최소값을 구하는 프로그램을 작성하자.


입력

입력은 다음 형식으로 표준 입력에서 제공됩니다.

H W

S_1

S_2

:

S_H

[제한]

1 ≤ H ≤ 500

1≤W≤500

(H, W) ≠ (1, 1)

S_i는 길이 W 의 문자열이다 ( 1≤i≤H )

S_i의 각 문자는 . 또는 # 이다 ( 1≤i≤H )

H, W는 정수다.


출력

조작을 반복하는 것으로 좌상의 매스로부터 우하의 매스에 조각을 도달시키는 것이 가능한 경우는 조작 횟수의 최소치를, 불가능한 경우를, 표준 출력에 1행으로 -1 출력 하라


부분문제

번호 점수 조건
#14점

H = 1

#214점

H ≤ 5 , W ≤ 5．

#324점

H ≤ 30 , W ≤ 30．

#458점

추가 제약은 없다.


예제1

입력
4 5
...#.
#####
...#.
#.###
출력
9

왼쪽의 예에서는 9 회의 조작으로, 오른쪽의 예에서는 13 회의 조작으로, 좌상단 칸에서 우하의단 칸에 조각을 도달시키는 것이 가능하다.

9 회보다 적은 조작 횟수로 도달하는 것은 불가능하기 때문에 9를 출력한다.

이 입력 예제는 작은 문제 2, 3, 4 의 제약 조건을 충족합니다.


예제2

입력
3 3
...
...
...
출력
-1

처음부터 조작을 할 수 없는 경우도 있다. 이 경우 조각을 오른쪽 하단의 칸에 도달 할 수 없으므로 -1 출력합니다.

이 입력 예제는 작은 문제 2, 3, 4 의 제약 조건을 충족합니다.


예제3

입력
1 5
.#.#.
출력
4

이 입력 예제는 모든 작은 문제의 제약 조건을 충족합니다.


예제4

입력
5 5
###.#
.#...
.#..#
.####
##..#
출력
12

이 입력 예제는 작은 문제 2, 3, 4 의 제약 조건을 충족합니다.


예제5

입력
7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.
출력
12

이 입력 예는 작은 문제 3, 4 의 제약 조건을 충족합니다.


출처

JOI 2022 예선2

역링크 공식 문제집만