시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 120 11 9 11.688%

문제

게임은 "장애물"로 표시된 몇 개의 사각형 셀이 있는 M × N 보드로 시작합니다 (장애물은 아래 그림에서 어두운 사각형으로 표시). 플레이어는 공의 시작 위치 (회색 점으로 표시)를 선택하고 진행 방향 (위, 아래, 왼쪽 또는 오른쪽)을 선택합니다. 방향이 선택되면 공은 장애물, 보드 경계 또는 자체 궤적에 도달 할 때까지 그 방향으로 움직입니다. 이것들 중 하나의 조건을 만족하면 공이 멈춥니다. 그런 다음, 플레이어는 다른 방향을 선택할 수 있으며 공은 선택된 방향으로 움직입니다. 공이 더이상 이동할 수 없을 때 게임이 종료됩니다. 궤적에 보드의 모든 빈 사각형 셀이 포함되어있는 경우에만 플레이어가 승리합니다. 아래 그림은 10 단계로 게임에서 승리하는 한 가지 방법을 보여주는 궤적을 추적합니다.

보드의 초기 설정이 주어질 때 게임에서 승리하기 위한 최소 단계 수를 계산하는 프로그램을 작성하십시오.

입력

1개 이상의 테스트 케이스가 주어질 수 있습니다. 각 테스트 케이스에 대한 입력의 첫 줄은 보드의 크기를 나타내는 두 개의 정수 m 및 n (1 ≤ m, n ≤ 30) 값이 주어집니다. 다음의 m 줄은 보드의 초기 설정을 나타냅니다. 각 줄에는 '*'또는 '.'문자가 n 개 포함되어 해당 사각형 셀이 각각 장애물인지 비어 있는지를 나타냅니다. (예를 들어, 아래 입력 예제는 위의 그림에 해당하는 내용을 입력값으로 나타낸 것입니다.) 주어진 보드가 장애물로만 완전히 덮여 있는 경우는 없습니다. 1개 이상의 테스트 케이스가 주어질 수 있기 때문에 입력의 끝까지 처리해야 합니다; 즉, 데이터 플래그의 끝이 없습니다.

출력

플레이어가 승리할 수 있는 최소 단계 수를 출력하십시오. 출력 형식을 정확히 따르십시오: Case, 한 칸 공백, 케이스 번호 (1부터 시작), 콜론, 한 칸 공백, 그리고 게임에서 승리하기 위한 최소 단계 수를 나타내는 정수 또는 승리 할 수있는 방법이 없는 경우 숫자 -1을 출력하세요. 후행 공백은 출력하지 마십시오.

예제 입력

5 5
**...
.....
....*
..*..
.....
3 4
****
*...
*..*

예제 출력

Case 1: 10
Case 2: 3

힌트