시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 88 19 14 42.424%

문제

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

Case 1: 10
Case 2: 3
W3sicHJvYmxlbV9pZCI6Ijk5NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJNeE4gXHViY2Y0XHViNGRjIFx1YzY0NFx1YzhmY1x1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHAgZGlyPVwibHRyXCI+XHVhYzhjXHVjNzg0XHVjNzQwICZxdW90O1x1YzdhNVx1YzU2MFx1YmIzYyZxdW90O1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MWMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjMTQwXHVjNzc0IFx1Yzc4OFx1YjI5NCBNICZ0aW1lczsgTiBcdWJjZjRcdWI0ZGNcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTY5XHViMmM4XHViMmU0IChcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NDAgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWM1YjRcdWI0NTBcdWM2YjQgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkYykuIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWFjZjVcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzcwNFx1Y2U1OCAoXHVkNjhjXHVjMGM5IFx1YzgxMFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGMpXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YWNlMCBcdWM5YzRcdWQ1ODkgXHViYzI5XHVkNWE1IChcdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjdjXHVjYWJkIFx1YjYxMFx1YjI5NCBcdWM2MjRcdWI5NzhcdWNhYmQpXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU2OVx1YjJjOFx1YjJlNC4gXHViYzI5XHVkNWE1XHVjNzc0IFx1YzEyMFx1ZDBkZFx1YjQxOFx1YmE3NCBcdWFjZjVcdWM3NDAgXHVjN2E1XHVjNTYwXHViYjNjLCBcdWJjZjRcdWI0ZGMgXHVhY2JkXHVhY2M0IFx1YjYxMFx1YjI5NCBcdWM3OTBcdWNjYjQgXHVhZGE0XHVjODAxXHVjNWQwIFx1YjNjNFx1YjJlYyBcdWQ1NjAgXHViNTRjXHVhZTRjXHVjOWMwIFx1YWRmOCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzg1XHViMmM4XHViMmU0LiBcdWM3NzRcdWFjODNcdWI0ZTQgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTc0IFx1YWNmNVx1Yzc3NCBcdWJhNDhcdWNkYTVcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjdmMCBcdWIyZTRcdWM3NGMsIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWIyZTRcdWI5NzggXHViYzI5XHVkNWE1XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwIFx1YWNmNVx1Yzc0MCBcdWMxMjBcdWQwZGRcdWI0MWMgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc4NVx1YjJjOFx1YjJlNC4gXHVhY2Y1XHVjNzc0IFx1YjM1NFx1Yzc3NFx1YzBjMSBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1Yzc0NCBcdWI1NGMgXHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzg4NVx1YjhjY1x1YjQyOVx1YjJjOFx1YjJlNC4gXHVhZGE0XHVjODAxXHVjNWQwIFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZTQ4IFx1YzBhY1x1YWMwMVx1ZDYxNSBcdWMxNDBcdWM3NzQgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjljYyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjMmI5XHViOWFjXHVkNTY5XHViMmM4XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIDEwIFx1YjJlOFx1YWNjNFx1Yjg1YyBcdWFjOGNcdWM3ODRcdWM1ZDBcdWMxMWMgXHVjMmI5XHViOWFjXHVkNTU4XHViMjk0IFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHVjNzQ0IFx1YmNmNFx1YzVlY1x1YzhmY1x1YjI5NCBcdWFkYTRcdWM4MDFcdWM3NDQgXHVjZDk0XHVjODAxXHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9mYm9hcmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjE5cHg7IHdpZHRoOjI0NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmNmNFx1YjRkY1x1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjMTI0XHVjODE1XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YzJiOVx1YjlhY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YjJlOFx1YWNjNCBcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZWRcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4xXHVhYzFjIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM3NDAgXHViY2Y0XHViNGRjXHVjNzU4IFx1ZDA2Y1x1YWUzMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggbSBcdWJjMGYgbiAoMSAmbGU7IG0sIG4gJmxlOyAzMCkgXHVhYzEyXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gXHViMmU0XHVjNzRjXHVjNzU4IG0gXHVjOTA0XHVjNzQwIFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWNkMDhcdWFlMzAgXHVjMTI0XHVjODE1XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBjNVx1YjJjOFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCAmIzM5OyomIzM5O1x1YjYxMFx1YjI5NCAmIzM5Oy4mIzM5O1x1YmIzOFx1Yzc5MFx1YWMwMCBuIFx1YWMxYyBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVkNTc0XHViMmY5IFx1YzBhY1x1YWMwMVx1ZDYxNSBcdWMxNDBcdWM3NzQgXHVhYzAxXHVhYzAxIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3OFx1YzljMCBcdWJlNDRcdWM1YjQgXHVjNzg4XHViMjk0XHVjOWMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBjNVx1YjJjOFx1YjJlNC4gKFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzU0NFx1Yjc5OCBcdWM3ODVcdWI4MjUgXHVjNjA4XHVjODFjXHViMjk0IFx1YzcwNFx1Yzc1OCBcdWFkZjhcdWI5YmNcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1YjBiNFx1YzZhOVx1Yzc0NCBcdWM3ODVcdWI4MjVcdWFjMTJcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4IFx1YWM4M1x1Yzc4NVx1YjJjOFx1YjJlNC4pIFx1YzhmY1x1YzViNFx1YzljNCBcdWJjZjRcdWI0ZGNcdWFjMDAgXHVjN2E1XHVjNTYwXHViYjNjXHViODVjXHViOWNjIFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWIzNmVcdWM1ZWMgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWMyYjVcdWIyYzhcdWIyZTQuIDFcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YzIxOCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWIwNWRcdWFlNGNcdWM5YzAgXHVjYzk4XHViOWFjXHVkNTc0XHVjNTdjIFx1ZDU2OVx1YjJjOFx1YjJlNDsgXHVjOTg5LCBcdWIzNzBcdWM3NzRcdWQxMzAgXHVkNTBjXHViNzk4XHVhZGY4XHVjNzU4IFx1YjA1ZFx1Yzc3NCBcdWM1YzZcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHAgZGlyPVwibHRyXCI+XHVkNTBjXHViODA4XHVjNzc0XHVjNWI0XHVhYzAwIFx1YzJiOVx1YjlhY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1Y2Q1Y1x1YzE4YyBcdWIyZThcdWFjYzQgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJlZFx1YzJkY1x1YzYyNC4gXHVjZDljXHViODI1IFx1ZDYxNVx1YzJkZFx1Yzc0NCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHViNTMwXHViOTc0XHVjMmVkXHVjMmRjXHVjNjI0OiBDYXNlLCBcdWQ1NWMgXHVjZTc4IFx1YWNmNVx1YmMzMSwgXHVjZjAwXHVjNzc0XHVjMmE0IFx1YmM4OFx1ZDYzOCAoMVx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWM3OTEpLCBcdWNmNWNcdWI4NjAsIFx1ZDU1YyBcdWNlNzggXHVhY2Y1XHViYzMxLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVhYzhjXHVjNzg0XHVjNWQwXHVjMTFjIFx1YzJiOVx1YjlhY1x1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YjJlOFx1YWNjNCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBcdWI2MTBcdWIyOTQgXHVjMmI5XHViOWFjIFx1ZDU2MCBcdWMyMThcdWM3ODhcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjAgXHVjMjJiXHVjNzkwIC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzEzOFx1YzY5NC4gXHVkNmM0XHVkNTg5IFx1YWNmNVx1YmMzMVx1Yzc0MCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM5YzAgXHViOWM4XHVjMmVkXHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk5NDQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGdWxsIEJvYXJkIiwiZGVzY3JpcHRpb24iOiI8cD5BIGdhbWUgc3RhcnRzIHdpdGggYW4gTSAmdGltZXM7IE4gYm9hcmQgd2l0aCBzb21lIHNxdWFyZXMgbWFya2VkIGFzICZsZHF1bztvYnN0YWNsZXMmcmRxdW87IChkcmF3biBhcyBkYXJrIHNxdWFyZXMgaW4gdGhlIGZpZ3VyZSBiZWxvdykuIFRoZSBwbGF5ZXIgY2hvb3NlcyBhIHN0YXJ0aW5nIHBvc2l0aW9uIGZvciBhIGJhbGwgKGRyYXduIGFzIHNvbGlkIGdyYXkgZG90KSBhbmQgY2hvb3NlcyBhIGRpcmVjdGlvbiAodXAsIGRvd24sIGxlZnQsIG9yIHJpZ2h0KSB0byBhZHZhbmNlLiBPbmNlIHRoZSBkaXJlY3Rpb24gaXMgY2hvc2VuLCB0aGUgYmFsbCB3aWxsIGFkdmFuY2UgaW4gdGhhdCBkaXJlY3Rpb24gdW50aWwgaXQgaGl0cyBhbiBvYnN0YWNsZSwgdGhlIGJvdW5kYXJ5IG9mIHRoZSBib2FyZCwgb3IgaXRzIG93biB0cmFqZWN0b3J5LiBXaGVuIGl0IGhpdHMgb25lIG9mIHRoZXNlLCB0aGUgYmFsbCBzdG9wcy4gVGhlbiB0aGUgcGxheWVyIGlzIGFsbG93ZWQgdG8gY2hvb3NlIGFub3RoZXIgZGlyZWN0aW9uLCBhbmQgdGhlIGJhbGwgd2lsbCBhZHZhbmNlIGluIHRoZSBzYW1lIG1hbm5lci4gVGhlIGdhbWUgZW5kcyB3aGVuIG5vIGxlZ2FsIG1vdmUgY2FuIGJlIG1hZGUuIFRoZSBwbGF5ZXIgd2lucyBpZiBhbmQgb25seSBpZiB0aGUgdHJhamVjdG9yeSBpbmNsdWRlcyBhbGwgdGhlIGVtcHR5IHNxdWFyZXMgb24gdGhlIGJvYXJkLiBUaGUgZmlndXJlIGJlbG93IHRyYWNlcyBhIHRyYWplY3RvcnkgdGhhdCBzaG93cyBvbmUgd2F5IHRvIHdpbiB0aGUgZ2FtZSBpbiAxMCBzdGVwcy48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZmJvYXJkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIxOXB4OyB3aWR0aDoyNDRweFwiIFwvPjxcL3A+XHJcblxyXG48cD5HaXZlbiBhbiBpbml0aWFsIHNldHRpbmcgb2YgYSBib2FyZCwgd3JpdGUgYSBwcm9ncmFtIHRvIGNhbGN1bGF0ZSB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3RlcHMgdG8gd2luIHRoZSBnYW1lLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+RWFjaCBjYXNlIG9uIHRoZSBpbnB1dCBmaWxlIGJlZ2lucyB3aXRoIHR3byBpbnRlZ2VycyBtIGFuZCBuICgxICZsZTsgbSwgbiAmbGU7IDMwKSwgaW5kaWNhdGluZyB0aGUgc2l6ZSBvZiBib2FyZC5UaGUgbmV4dCBtIGxpbmVzIGRlc2NyaWJlIHRoZSBpbml0aWFsIHNldHRpbmcgb2YgdGhlIGJvYXJkLiBFYWNoIGxpbmUgY29udGFpbnMgbiBjaGFyYWN0ZXJzLCBlaXRoZXIgJmxzcXVvOyomcnNxdW87IG9yICZsc3F1bzsuJnJzcXVvOywgaW5kaWNhdGluZyBpZiB0aGUgY29ycmVzcG9uZGluZyBzcXVhcmUgaXMgYW4gb2JzdGFjbGUgb3IgZW1wdHksIHJlc3BlY3RpdmVseS4gW0ZvciBleGFtcGxlLCBzZWUgYmVsb3cgZm9yIHRoZSBpbnB1dCBmaWxlIGNvcnJlc3BvbmRpbmcgdG8gdGhlIGNhc2UgaW4gdGhlIGZpZ3VyZSBhYm92ZS5dIEl0IGlzIGd1YXJhbnRlZWQgdGhhdCB0aGUgaW5pdGlhbCBib2FyZCBpcyBub3QgZnVsbHkgY292ZXJlZCBieSBvYnN0YWNsZXMuIFByb2Nlc3MgdW50aWwgZW5kLW9mLWZpbGU7IHRoZXJlIGlzIG5vIGVuZCBvZiBkYXRhIGZsYWcuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGVwcyB0byBjb3ZlciB0aGUgYm9hcmQuIEZvbGxvdyB0aGUgZm9ybWF0IGV4YWN0bHk6ICZsZHF1bztDYXNlJnJkcXVvOywgb25lIHNwYWNlLCB0aGUgY2FzZSBudW1iZXIsIGEgY29sb24gYW5kIG9uZSBzcGFjZSwgYW5kIG9uZSBpbnRlZ2VyIGluZGljYXRpbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0ZXBzIHRvIHdpbiB0aGUgZ2FtZSwgb3IgaWYgdGhlcmUgaXMgbm8gd2F5IHRvIHdpbiwgdGhlIG51bWJlciAtMS4gRG8gbm90IHByaW50IGFueSB0cmFpbGluZyBzcGFjZXM8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=