시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 229 42 27 39.706%

문제

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

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

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

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

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

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

입력

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

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

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

출력

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

만약, 모든 빈 칸을 방문할 수 없다면 최소 이동 횟수는 -1이다.

예제 입력 1

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

예제 출력 1

Case 1: 10
Case 2: 3
W3sicHJvYmxlbV9pZCI6Ijk5NDQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOeE0gXHViY2Y0XHViNGRjIFx1YzY0NFx1YzhmY1x1ZDU1OFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHAgZGlyPVwibHRyXCI+TiZ0aW1lcztNIFx1YmNmNFx1YjRkYyBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViY2Y0XHViNGRjXHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCAxJnRpbWVzOzFcdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM4MDBcdWM1ZWMgXHVjNzg4XHViMmU0LiBcdWJjZjRcdWI0ZGNcdWM3NTggXHVhYzAxIFx1Y2U3OFx1Yzc0MCBcdWJlNDggXHVjZTc4IFx1YjYxMFx1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzRcdWIyZTQuIFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc0MCBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTIwIFx1YzViNFx1YjQ1MFx1YzZiNCBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHAgZGlyPVwibHRyXCI+XHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWJjZjRcdWI0ZGNcdWM3NTggXHViZTQ4IFx1Y2U3OCBcdWM3MDRcdWM1ZDAmbmJzcDtcdWFjZjVcdWM3NDQmbmJzcDtcdWQ1NThcdWIwOTggXHViMTkzXHVjNTQ0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNWQwXHVjMTFjIFx1YWNmNVx1Yzc0MCBcdWQ2OGNcdWMwYzkgXHVjODEwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWIyZThcdWFjYzRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YjJlOFx1YWNjNFx1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjx1bCBkaXI9XCJsdHJcIj5cclxuXHQ8bGk+XHVjNzA0LCBcdWM1NDRcdWI3OTgsIFx1YzYyNFx1Yjk3OFx1Y2FiZCwgXHVjNjdjXHVjYWJkIFx1YzkxMSBcdWJjMjlcdWQ1YTUgXHVkNTU4XHViMDk4XHViOTdjIFx1YWNlMFx1Yjk3OCBcdWIyZTRcdWM3NGMsIFx1YWRmOCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVhY2Y1XHVjNzQ0IFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWMyZGNcdWQwYThcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YWNmNVx1Yzc0MCBcdWM3YTVcdWM1NjBcdWJiM2MsIFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWFjYmRcdWFjYzQsIFx1Yzc3NFx1YmJmOCBcdWFjZjVcdWM3NzQgXHVjOWMwXHViMDk4XHVhYzE0XHViMzU4IFx1Y2U3OFx1Yzc0NCBcdWI5Y2NcdWIwOThcdWFlMzAgXHVjODA0XHVhZTRjXHVjOWMwIFx1YWNjNFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIFx1YWNmNVx1Yzc3NCBcdWIzNTQgXHVjNzc0XHVjMGMxIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVjNzQ0IFx1YjU0YyZuYnNwO1x1YjA1ZFx1YjA5Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHVhY2Y1XHVjNzc0IFx1YmMyOVx1YmIzOFx1ZDU1YyBcdWM4MDFcdWM3NzQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWNkMWQgMTBcdWIyZThcdWFjYzQgXHViOWNjXHVjNWQwIFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvZmJvYXJkLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OiAxNTBweDsgd2lkdGg6IDE2N3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJjZjRcdWI0ZGNcdWM3NTggXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM3NDQgXHViYzI5XHViYjM4XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWM3NzRcdWIzZDkgXHVkNjlmXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjZjRcdWI0ZGNcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBOXHVhY2ZjIE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIFx1YzEzOFx1Yjg1YyBcdWQwNmNcdWFlMzAsIE1cdWM3NDAgXHVhYzAwXHViODVjIFx1ZDA2Y1x1YWUzMFx1Yzc3NFx1YWNlMCwgXHViNDUwIFx1YWMxMlx1Yzc0MCAzMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjZjRcdWI0ZGNcdWM3NTggXHVjMGMxXHVkMGRjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViY2Y0XHViNGRjXHVjNzU4IFx1YzBjMVx1ZDBkY1x1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0ICYjMzk7KiYjMzk7XHVhY2ZjIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0Jm5ic3A7JiMzOTsuJiMzOTtcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWJjZjRcdWI0ZGNcdWFjMDAgXHVjN2E1XHVjNTYwXHViYjNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwIGRpcj1cImx0clwiPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWJhYThcdWI0ZTAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHVjZDVjXHVjMThjIFx1Yzc3NFx1YjNkOSBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjUgXHVkNjE1XHVjMmRkXHVjNzQwIFx1YzYwOFx1YzgxY1x1Yjk3YyBcdWNjMzhcdWFjZTBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwIGRpcj1cImx0clwiPlx1YjljY1x1YzU3ZCwgXHViYWE4XHViNGUwIFx1YmU0OCBcdWNlNzhcdWM3NDQgXHViYzI5XHViYjM4XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgXHVjZDVjXHVjMThjIFx1Yzc3NFx1YjNkOSBcdWQ2OWZcdWMyMThcdWIyOTQgLTFcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTk0NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZ1bGwgQm9hcmQiLCJkZXNjcmlwdGlvbiI6IjxwPkEgZ2FtZSBzdGFydHMgd2l0aCBhbiBNICZ0aW1lczsgTiBib2FyZCB3aXRoIHNvbWUgc3F1YXJlcyBtYXJrZWQgYXMgJmxkcXVvO29ic3RhY2xlcyZyZHF1bzsgKGRyYXduIGFzIGRhcmsgc3F1YXJlcyBpbiB0aGUgZmlndXJlIGJlbG93KS4gVGhlIHBsYXllciBjaG9vc2VzIGEgc3RhcnRpbmcgcG9zaXRpb24gZm9yIGEgYmFsbCAoZHJhd24gYXMgc29saWQgZ3JheSBkb3QpIGFuZCBjaG9vc2VzIGEgZGlyZWN0aW9uICh1cCwgZG93biwgbGVmdCwgb3IgcmlnaHQpIHRvIGFkdmFuY2UuIE9uY2UgdGhlIGRpcmVjdGlvbiBpcyBjaG9zZW4sIHRoZSBiYWxsIHdpbGwgYWR2YW5jZSBpbiB0aGF0IGRpcmVjdGlvbiB1bnRpbCBpdCBoaXRzIGFuIG9ic3RhY2xlLCB0aGUgYm91bmRhcnkgb2YgdGhlIGJvYXJkLCBvciBpdHMgb3duIHRyYWplY3RvcnkuIFdoZW4gaXQgaGl0cyBvbmUgb2YgdGhlc2UsIHRoZSBiYWxsIHN0b3BzLiBUaGVuIHRoZSBwbGF5ZXIgaXMgYWxsb3dlZCB0byBjaG9vc2UgYW5vdGhlciBkaXJlY3Rpb24sIGFuZCB0aGUgYmFsbCB3aWxsIGFkdmFuY2UgaW4gdGhlIHNhbWUgbWFubmVyLiBUaGUgZ2FtZSBlbmRzIHdoZW4gbm8gbGVnYWwgbW92ZSBjYW4gYmUgbWFkZS4gVGhlIHBsYXllciB3aW5zIGlmIGFuZCBvbmx5IGlmIHRoZSB0cmFqZWN0b3J5IGluY2x1ZGVzIGFsbCB0aGUgZW1wdHkgc3F1YXJlcyBvbiB0aGUgYm9hcmQuIFRoZSBmaWd1cmUgYmVsb3cgdHJhY2VzIGEgdHJhamVjdG9yeSB0aGF0IHNob3dzIG9uZSB3YXkgdG8gd2luIHRoZSBnYW1lIGluIDEwIHN0ZXBzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9mYm9hcmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjE5cHg7IHdpZHRoOjI0NHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkdpdmVuIGFuIGluaXRpYWwgc2V0dGluZyBvZiBhIGJvYXJkLCB3cml0ZSBhIHByb2dyYW0gdG8gY2FsY3VsYXRlIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGVwcyB0byB3aW4gdGhlIGdhbWUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIGNhc2Ugb24gdGhlIGlucHV0IGZpbGUgYmVnaW5zIHdpdGggdHdvIGludGVnZXJzIG0gYW5kIG4gKDEgJmxlOyBtLCBuICZsZTsgMzApLCBpbmRpY2F0aW5nIHRoZSBzaXplIG9mIGJvYXJkLlRoZSBuZXh0IG0gbGluZXMgZGVzY3JpYmUgdGhlIGluaXRpYWwgc2V0dGluZyBvZiB0aGUgYm9hcmQuIEVhY2ggbGluZSBjb250YWlucyBuIGNoYXJhY3RlcnMsIGVpdGhlciAmbHNxdW87KiZyc3F1bzsgb3IgJmxzcXVvOy4mcnNxdW87LCBpbmRpY2F0aW5nIGlmIHRoZSBjb3JyZXNwb25kaW5nIHNxdWFyZSBpcyBhbiBvYnN0YWNsZSBvciBlbXB0eSwgcmVzcGVjdGl2ZWx5LiBbRm9yIGV4YW1wbGUsIHNlZSBiZWxvdyBmb3IgdGhlIGlucHV0IGZpbGUgY29ycmVzcG9uZGluZyB0byB0aGUgY2FzZSBpbiB0aGUgZmlndXJlIGFib3ZlLl0gSXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZSBpbml0aWFsIGJvYXJkIGlzIG5vdCBmdWxseSBjb3ZlcmVkIGJ5IG9ic3RhY2xlcy4gUHJvY2VzcyB1bnRpbCBlbmQtb2YtZmlsZTsgdGhlcmUgaXMgbm8gZW5kIG9mIGRhdGEgZmxhZy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0ZXBzIHRvIGNvdmVyIHRoZSBib2FyZC4gRm9sbG93IHRoZSBmb3JtYXQgZXhhY3RseTogJmxkcXVvO0Nhc2UmcmRxdW87LCBvbmUgc3BhY2UsIHRoZSBjYXNlIG51bWJlciwgYSBjb2xvbiBhbmQgb25lIHNwYWNlLCBhbmQgb25lIGludGVnZXIgaW5kaWNhdGluZyB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3RlcHMgdG8gd2luIHRoZSBnYW1lLCBvciBpZiB0aGVyZSBpcyBubyB3YXkgdG8gd2luLCB0aGUgbnVtYmVyIC0xLiBEbyBub3QgcHJpbnQgYW55IHRyYWlsaW5nIHNwYWNlczxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==