카펫 (Carpet)
면접 대비시간 제한2초메모리 제한1024 MB
흰색과 검은색 칸으로 이루어진 격자에서 시작점에서 도착점까지 인접한 반대 색 칸으로만 이동할 때 최소 이동 횟수를 구하고, 도달할 수 없으면 -1을 출력한다.
문제
멋 부리기를 좋아하는 비타로는 카펫을 새로 샀다. 카펫은 세로 H행, 가로 W열의 격자 모양으로 나뉜 직사각형이고, 각 칸은 흰색이나 검은색 중 하나로 칠해져 있다. 카펫의 위에서 i번째 행, 왼쪽에서 j번째 열 (1 ≦ i ≦ H, 1 ≦ j ≦ W)에 있는 칸의 색은 문자열 Si의 j번째 문자가 .이면 흰색, #이면 검은색이다.
비타로는 카펫의 가장 왼쪽 위 칸에 말을 놓고, 다음 연산을 몇 번이든 반복해 그 말을 카펫의 가장 오른쪽 아래 칸에 도착시키는 놀이를 생각해 냈다.
- 말이 놓인 칸과 색이 다르고, 상하좌우로 인접한 칸을
1개 골라 그 칸으로 말을 옮긴다.
비타로는 도착할 때까지의 연산 횟수를 최대한 줄이고 싶어 한다. 다만 카펫의 무늬에 따라서는 도착시키지 못할 수도 있다.
카펫의 무늬 정보가 주어졌을 때, 연산을 반복해 왼쪽 위 칸에서 오른쪽 아래 칸으로 말을 도착시킬 수 있는지 판정하고, 가능하면 연산 횟수의 최솟값을 구하는 프로그램을 작성하시오.
입력
입력은 다음 형식으로 표준 입력에서 주어진다.
H W
S1
S2
:
SH
출력
연산을 반복해 왼쪽 위 칸에서 오른쪽 아래 칸으로 말을 도착시킬 수 있으면 연산 횟수의 최솟값을, 불가능하면 -1을 표준 출력에 1행으로 출력하시오.
제한
1 ≦ H ≦ 500.1 ≦ W ≦ 500.(H, W) ≠ (1, 1).Si는 길이W의 문자열이다 (1 ≦ i ≦ H).Si의 각 문자는.또는#이다 (1 ≦ i ≦ H).H, W는 정수이다.