시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (하단 참고)256 MB3718120678330.302%

문제

N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 있다.

게임을 시작하려면 보드의 빈 칸 위에 공을 하나 놓아야 한다. 아래 그림에서 공은 회색 점으로 표시되어져 있다. 게임은 단계로 이루어져 있고, 각 단계는 아래와 같이 구성되어져 있다.

  • 위, 아래, 오른쪽, 왼쪽 중 방향 하나를 고른 다음, 그 방향으로 공을 계속해서 이동시킨다.
  • 공은 장애물, 보드의 경계, 이미 공이 지나갔던 칸을 만나기 전까지 계속해서 이동한다.

게임은 공이 더 이상 이동할 수 없을 때 끝난다. 이 때, 모든 빈 칸을 공이 방문한 적이 있어야 한다.

아래 그림은 총 10단계 만에 모든 칸을 방문하는 방법이다.

보드의 상태가 주어졌을 때, 모든 칸을 방문하기 위한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 보드의 크기를 나타내는 N과 M이 주어진다. N은 세로 크기, M은 가로 크기이고, 두 값은 30보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 상태가 주어진다. 보드의 상태는 장애물을 나타내는 '*'과 빈 칸을 나타내는 '.'으로 이루어져 있다.

입력으로 주어진 보드가 장애물로만 이루어진 경우는 없다.

출력

각 테스트 케이스마다 보드의 모든 빈 칸을 방문하는 최소 이동 횟수를 출력한다. 출력 형식은 예제를 참고한다.

만약, 모든 빈 칸을 방문할 수 없다면 최소 이동 횟수는 -1이다. 가능한 이동 경로의 수는 1,000,000개를 넘지 않는다.

예제 입력 1

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

예제 출력 1

Case 1: 10
Case 2: 3
W3sicHJvYmxlbV9pZCI6Ijk5NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOeE0gXHViY2Y0XHViNGRjIFx1YzY0NFx1YzhmY1x1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHAgZGlyPVwibHRyXCI+TiZ0aW1lcztNIFx1YmNmNFx1YjRkYyBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViY2Y0XHViNGRjXHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCAxJnRpbWVzOzFcdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzgmbmJzcDtcdWM3ODhcdWIyZTQuIFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1YmU0OCBcdWNlNzggXHViNjEwXHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3NFx1YjJlNC4gXHVjN2E1XHVjNTYwXHViYjNjXHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMjAgXHVjNWI0XHViNDUwXHVjNmI0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBkaXI9XCJsdHJcIj5cdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViODI0XHViYTc0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWJlNDggXHVjZTc4IFx1YzcwNFx1YzVkMCZuYnNwO1x1YWNmNVx1Yzc0NCZuYnNwO1x1ZDU1OFx1YjA5OCBcdWIxOTNcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwO1x1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVhY2Y1XHVjNzQwIFx1ZDY4Y1x1YzBjOSBcdWM4MTBcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjJlOFx1YWNjNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViMmU4XHVhY2M0XHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsIGRpcj1cImx0clwiPlxyXG5cdDxsaT5cdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM2N2NcdWNhYmQgXHVjOTExIFx1YmMyOVx1ZDVhNSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2UwXHViOTc4IFx1YjJlNFx1Yzc0YywgXHVhZGY4IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWFjZjVcdWM3NDQgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1YzJkY1x1ZDBhOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhY2Y1XHVjNzQwIFx1YzdhNVx1YzU2MFx1YmIzYywgXHViY2Y0XHViNGRjXHVjNzU4IFx1YWNiZFx1YWNjNCwgXHVjNzc0XHViYmY4IFx1YWNmNVx1Yzc3NCBcdWM5YzBcdWIwOThcdWFjMTRcdWIzNTggXHVjZTc4XHVjNzQ0IFx1YjljY1x1YjA5OFx1YWUzMCBcdWM4MDRcdWFlNGNcdWM5YzAgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgXHVhY2Y1XHVjNzc0IFx1YjM1NCBcdWM3NzRcdWMwYzEgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWM3NDQgXHViNTRjJm5ic3A7XHViMDVkXHViMDljXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWFjZjVcdWM3NzQgXHViYzI5XHViYjM4XHVkNTVjIFx1YzgwMVx1Yzc3NCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1Y2QxZCAxMFx1YjJlOFx1YWNjNCBcdWI5Y2NcdWM1ZDAgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9mYm9hcmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6IDE1MHB4OyB3aWR0aDogMTY3cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmNmNFx1YjRkY1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1Yzc3NFx1YjNkOSBcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjMTM4XHViODVjIFx1ZDA2Y1x1YWUzMCwgTVx1Yzc0MCBcdWFjMDBcdWI4NWMgXHVkMDZjXHVhZTMwXHVjNzc0XHVhY2UwLCBcdWI0NTAgXHVhYzEyXHVjNzQwIDMwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjZjRcdWI0ZGNcdWM3NTggXHVjMGMxXHVkMGRjXHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgJiMzOTsqJiMzOTtcdWFjZmMgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQmbmJzcDsmIzM5Oy4mIzM5O1x1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmNmNFx1YjRkY1x1YWMwMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHAgZGlyPVwibHRyXCI+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViY2Y0XHViNGRjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNSBcdWQ2MTVcdWMyZGRcdWM3NDAgXHVjNjA4XHVjODFjXHViOTdjIFx1Y2MzOFx1YWNlMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgZGlyPVwibHRyXCI+XHViOWNjXHVjNTdkLCBcdWJhYThcdWI0ZTAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCBcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1YjI5NCAtMVx1Yzc3NFx1YjJlNC4mbmJzcDtcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzc0XHViM2Q5IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWMyMThcdWIyOTQgMSwwMDAsMDAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTk0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZ1bGwgQm9hcmQiLCJkZXNjcmlwdGlvbiI6IjxwPkEgZ2FtZSBzdGFydHMgd2l0aCBhbiBNICZ0aW1lczsgTiBib2FyZCB3aXRoIHNvbWUgc3F1YXJlcyBtYXJrZWQgYXMgJmxkcXVvO29ic3RhY2xlcyZyZHF1bzsgKGRyYXduIGFzIGRhcmsgc3F1YXJlcyBpbiB0aGUgZmlndXJlIGJlbG93KS4gVGhlIHBsYXllciBjaG9vc2VzIGEgc3RhcnRpbmcgcG9zaXRpb24gZm9yIGEgYmFsbCAoZHJhd24gYXMgc29saWQgZ3JheSBkb3QpIGFuZCBjaG9vc2VzIGEgZGlyZWN0aW9uICh1cCwgZG93biwgbGVmdCwgb3IgcmlnaHQpIHRvIGFkdmFuY2UuIE9uY2UgdGhlIGRpcmVjdGlvbiBpcyBjaG9zZW4sIHRoZSBiYWxsIHdpbGwgYWR2YW5jZSBpbiB0aGF0IGRpcmVjdGlvbiB1bnRpbCBpdCBoaXRzIGFuIG9ic3RhY2xlLCB0aGUgYm91bmRhcnkgb2YgdGhlIGJvYXJkLCBvciBpdHMgb3duIHRyYWplY3RvcnkuIFdoZW4gaXQgaGl0cyBvbmUgb2YgdGhlc2UsIHRoZSBiYWxsIHN0b3BzLiBUaGVuIHRoZSBwbGF5ZXIgaXMgYWxsb3dlZCB0byBjaG9vc2UgYW5vdGhlciBkaXJlY3Rpb24sIGFuZCB0aGUgYmFsbCB3aWxsIGFkdmFuY2UgaW4gdGhlIHNhbWUgbWFubmVyLiBUaGUgZ2FtZSBlbmRzIHdoZW4gbm8gbGVnYWwgbW92ZSBjYW4gYmUgbWFkZS4gVGhlIHBsYXllciB3aW5zIGlmIGFuZCBvbmx5IGlmIHRoZSB0cmFqZWN0b3J5IGluY2x1ZGVzIGFsbCB0aGUgZW1wdHkgc3F1YXJlcyBvbiB0aGUgYm9hcmQuIFRoZSBmaWd1cmUgYmVsb3cgdHJhY2VzIGEgdHJhamVjdG9yeSB0aGF0IHNob3dzIG9uZSB3YXkgdG8gd2luIHRoZSBnYW1lIGluIDEwIHN0ZXBzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9mYm9hcmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjE5cHg7IHdpZHRoOjI0NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkdpdmVuIGFuIGluaXRpYWwgc2V0dGluZyBvZiBhIGJvYXJkLCB3cml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGVwcyB0byB3aW4gdGhlIGdhbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGNhc2Ugb24gdGhlIGlucHV0IGZpbGUgYmVnaW5zIHdpdGggdHdvIGludGVnZXJzIG0gYW5kIG4gKDEgJmxlOyBtLCBuICZsZTsgMzApLCBpbmRpY2F0aW5nIHRoZSBzaXplIG9mIGJvYXJkLlRoZSBuZXh0IG0gbGluZXMgZGVzY3JpYmUgdGhlIGluaXRpYWwgc2V0dGluZyBvZiB0aGUgYm9hcmQuIEVhY2ggbGluZSBjb250YWlucyBuIGNoYXJhY3RlcnMsIGVpdGhlciAmbHNxdW87KiZyc3F1bzsgb3IgJmxzcXVvOy4mcnNxdW87LCBpbmRpY2F0aW5nIGlmIHRoZSBjb3JyZXNwb25kaW5nIHNxdWFyZSBpcyBhbiBvYnN0YWNsZSBvciBlbXB0eSwgcmVzcGVjdGl2ZWx5LiBbRm9yIGV4YW1wbGUsIHNlZSBiZWxvdyBmb3IgdGhlIGlucHV0IGZpbGUgY29ycmVzcG9uZGluZyB0byB0aGUgY2FzZSBpbiB0aGUgZmlndXJlIGFib3ZlLl0gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBpbml0aWFsIGJvYXJkIGlzIG5vdCBmdWxseSBjb3ZlcmVkIGJ5IG9ic3RhY2xlcy4gUHJvY2VzcyB1bnRpbCBlbmQtb2YtZmlsZTsgdGhlcmUgaXMgbm8gZW5kIG9mIGRhdGEgZmxhZy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0ZXBzIHRvIGNvdmVyIHRoZSBib2FyZC4gRm9sbG93IHRoZSBmb3JtYXQgZXhhY3RseTogJmxkcXVvO0Nhc2UmcmRxdW87LCBvbmUgc3BhY2UsIHRoZSBjYXNlIG51bWJlciwgYSBjb2xvbiBhbmQgb25lIHNwYWNlLCBhbmQgb25lIGludGVnZXIgaW5kaWNhdGluZyB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3RlcHMgdG8gd2luIHRoZSBnYW1lLCBvciBpZiB0aGVyZSBpcyBubyB3YXkgdG8gd2luLCB0aGUgbnVtYmVyIC0xLiBEbyBub3QgcHJpbnQgYW55IHRyYWlsaW5nIHNwYWNlczxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > North Central North America Regional > NCNA 2013 F번

  • 빠진 조건을 찾은 사람: jh05013
  • 문제의 오타를 찾은 사람: sky1357

시간 제한

  • Python 3: 30 초
  • PyPy3: 30 초
  • Python 2: 30 초
  • PyPy2: 30 초