나무 숲
면접 대비시간 제한1초메모리 제한1024 MB
R행 C열 격자에서 X로 표시된 숲을 한 바퀴 돌아 시작 위치로 돌아오는 최소 이동 횟수를 구합니다.
문제
목장에 구멍이 없는 작고 연결된 나무 숲이 하나 있다. 베시는 이 숲을 한 바퀴 돌아 출발 위치로 돌아오려면 몇 걸음이 필요한지 궁금해한다. 베시는 시작 위치에서 수평, 수직, 대각선 방향으로 한 칸씩 걸어 차례대로 다른 위치를 거치면 반드시 한 바퀴를 돌 수 있다고 확신한다. 한눈에 보기에도 교묘한 대각선 이동으로 숲의 가운데를 가로질러 지나갈 수는 없어 보인다. 베시가 밟아야 하는 최소 걸음 수를 구하라.
목장은 R행 C열의 격자이다 (1 ≤ R ≤ 50, 1 ≤ C ≤ 50). 아래 예시에서 '.'은 베시가 걸을 수 있는 목장, 'X'는 나무 숲, '*'는 베시의 시작 및 도착 위치이며, '+'는 숲을 도는 최단 경로 중 하나로 정답에 해당한다.
...+...
..+X+..
.+XXX+.
..+XXX+
..+X..+
...+++*
그림의 경로가 유일한 최단 경로는 아니다. 베시는 시작 위치에서 대각선으로 한 걸음 내디뎌도 비슷한 길이의 해를 얻을 수 있다. 시작 위치가 숲 바깥이어서 최단 경로를 찾기 어렵게 만드는 항구 같은 구역에서 출발하지 않는 것은 다행이다.
입력
첫 줄에 공백으로 구분된 두 정수 R과 C가 주어진다. 이어지는 R개 줄에서 i+1번째 줄은 i행을 나타내며, 공백 없이 C개의 문자로 이루어진다.
출력
베시가 숲을 한 바퀴 돌아 시작 위치로 돌아오는 데 필요한 최소 걸음 수를 한 줄에 출력한다.