시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (하단 참고) 256 MB 346 74 53 35.570%

문제

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+TiZ0aW1lcztNIFx1YmNmNFx1YjRkYyBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHViY2Y0XHViNGRjXHViMjk0IFx1ZDA2Y1x1YWUzMFx1YWMwMCAxJnRpbWVzOzFcdWM3NzggXHVjODE1XHVjMGFjXHVhYzAxXHVkNjE1IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDRcdWM1YjRcdWM4MzgmbmJzcDtcdWM3ODhcdWIyZTQuIFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWFjMDEgXHVjZTc4XHVjNzQwIFx1YmU0OCBcdWNlNzggXHViNjEwXHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc3NFx1YjJlNC4gXHVjN2E1XHVjNTYwXHViYjNjXHVjNzQwIFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMjAgXHVjNWI0XHViNDUwXHVjNmI0IFx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cCBkaXI9XCJsdHJcIj5cdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViODI0XHViYTc0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWJlNDggXHVjZTc4IFx1YzcwNFx1YzVkMCZuYnNwO1x1YWNmNVx1Yzc0NCZuYnNwO1x1ZDU1OFx1YjA5OCBcdWIxOTNcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwO1x1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVhY2Y1XHVjNzQwIFx1ZDY4Y1x1YzBjOSBcdWM4MTBcdWM3M2NcdWI4NWMgXHVkNDVjXHVjMmRjXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjJlOFx1YWNjNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViMmU4XHVhY2M0XHViMjk0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHVhZDZjXHVjMTMxXHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHVsIGRpcj1cImx0clwiPlxyXG5cdDxsaT5cdWM3MDQsIFx1YzU0NFx1Yjc5OCwgXHVjNjI0XHViOTc4XHVjYWJkLCBcdWM2N2NcdWNhYmQgXHVjOTExIFx1YmMyOVx1ZDVhNSBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2UwXHViOTc4IFx1YjJlNFx1Yzc0YywgXHVhZGY4IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWFjZjVcdWM3NDQgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1YzJkY1x1ZDBhOFx1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVhY2Y1XHVjNzQwIFx1YzdhNVx1YzU2MFx1YmIzYywgXHViY2Y0XHViNGRjXHVjNzU4IFx1YWNiZFx1YWNjNCwgXHVjNzc0XHViYmY4IFx1YWNmNVx1Yzc3NCBcdWM5YzBcdWIwOThcdWFjMTRcdWIzNTggXHVjZTc4XHVjNzQ0IFx1YjljY1x1YjA5OFx1YWUzMCBcdWM4MDRcdWFlNGNcdWM5YzAgXHVhY2M0XHVjMThkXHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgXHVhY2Y1XHVjNzc0IFx1YjM1NCBcdWM3NzRcdWMwYzEgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWM3NDQgXHViNTRjJm5ic3A7XHViMDVkXHViMDljXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWFjZjVcdWM3NzQgXHViYzI5XHViYjM4XHVkNTVjIFx1YzgwMVx1Yzc3NCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1Y2QxZCAxMFx1YjJlOFx1YWNjNCBcdWI5Y2NcdWM1ZDAgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9mYm9hcmQucG5nXCIgc3R5bGU9XCJoZWlnaHQ6IDE1MHB4OyB3aWR0aDogMTY3cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YmNmNFx1YjRkY1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1Y2U3OFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTVjIFx1Yzc3NFx1YjNkOSBcdWQ2OWZcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWQwNmNcdWFlMzBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE5cdWFjZmMgTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgXHVjMTM4XHViODVjIFx1ZDA2Y1x1YWUzMCwgTVx1Yzc0MCBcdWFjMDBcdWI4NWMgXHVkMDZjXHVhZTMwXHVjNzc0XHVhY2UwLCBcdWI0NTAgXHVhYzEyXHVjNzQwIDMwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmNmNFx1YjRkY1x1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJjZjRcdWI0ZGNcdWM3NTggXHVjMGMxXHVkMGRjXHViMjk0IFx1YzdhNVx1YzU2MFx1YmIzY1x1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgJiMzOTsqJiMzOTtcdWFjZmMgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQmbmJzcDsmIzM5Oy4mIzM5O1x1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmNmNFx1YjRkY1x1YWMwMCBcdWM3YTVcdWM1NjBcdWJiM2NcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHAgZGlyPVwibHRyXCI+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHViY2Y0XHViNGRjXHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJlNDggXHVjZTc4XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2Q5Y1x1YjgyNSBcdWQ2MTVcdWMyZGRcdWM3NDAgXHVjNjA4XHVjODFjXHViOTdjIFx1Y2MzOFx1YWNlMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHAgZGlyPVwibHRyXCI+XHViOWNjXHVjNTdkLCBcdWJhYThcdWI0ZTAgXHViZTQ4IFx1Y2U3OFx1Yzc0NCBcdWJjMjlcdWJiMzhcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCBcdWNkNWNcdWMxOGMgXHVjNzc0XHViM2Q5IFx1ZDY5Zlx1YzIxOFx1YjI5NCAtMVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5OTQ0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRnVsbCBCb2FyZCIsImRlc2NyaXB0aW9uIjoiPHA+QSBnYW1lIHN0YXJ0cyB3aXRoIGFuIE0gJnRpbWVzOyBOIGJvYXJkIHdpdGggc29tZSBzcXVhcmVzIG1hcmtlZCBhcyAmbGRxdW87b2JzdGFjbGVzJnJkcXVvOyAoZHJhd24gYXMgZGFyayBzcXVhcmVzIGluIHRoZSBmaWd1cmUgYmVsb3cpLiBUaGUgcGxheWVyIGNob29zZXMgYSBzdGFydGluZyBwb3NpdGlvbiBmb3IgYSBiYWxsIChkcmF3biBhcyBzb2xpZCBncmF5IGRvdCkgYW5kIGNob29zZXMgYSBkaXJlY3Rpb24gKHVwLCBkb3duLCBsZWZ0LCBvciByaWdodCkgdG8gYWR2YW5jZS4gT25jZSB0aGUgZGlyZWN0aW9uIGlzIGNob3NlbiwgdGhlIGJhbGwgd2lsbCBhZHZhbmNlIGluIHRoYXQgZGlyZWN0aW9uIHVudGlsIGl0IGhpdHMgYW4gb2JzdGFjbGUsIHRoZSBib3VuZGFyeSBvZiB0aGUgYm9hcmQsIG9yIGl0cyBvd24gdHJhamVjdG9yeS4gV2hlbiBpdCBoaXRzIG9uZSBvZiB0aGVzZSwgdGhlIGJhbGwgc3RvcHMuIFRoZW4gdGhlIHBsYXllciBpcyBhbGxvd2VkIHRvIGNob29zZSBhbm90aGVyIGRpcmVjdGlvbiwgYW5kIHRoZSBiYWxsIHdpbGwgYWR2YW5jZSBpbiB0aGUgc2FtZSBtYW5uZXIuIFRoZSBnYW1lIGVuZHMgd2hlbiBubyBsZWdhbCBtb3ZlIGNhbiBiZSBtYWRlLiBUaGUgcGxheWVyIHdpbnMgaWYgYW5kIG9ubHkgaWYgdGhlIHRyYWplY3RvcnkgaW5jbHVkZXMgYWxsIHRoZSBlbXB0eSBzcXVhcmVzIG9uIHRoZSBib2FyZC4gVGhlIGZpZ3VyZSBiZWxvdyB0cmFjZXMgYSB0cmFqZWN0b3J5IHRoYXQgc2hvd3Mgb25lIHdheSB0byB3aW4gdGhlIGdhbWUgaW4gMTAgc3RlcHMuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2Zib2FyZC5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTlweDsgd2lkdGg6MjQ0cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYW4gaW5pdGlhbCBzZXR0aW5nIG9mIGEgYm9hcmQsIHdyaXRlIGEgcHJvZ3JhbSB0byBjYWxjdWxhdGUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHN0ZXBzIHRvIHdpbiB0aGUgZ2FtZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggY2FzZSBvbiB0aGUgaW5wdXQgZmlsZSBiZWdpbnMgd2l0aCB0d28gaW50ZWdlcnMgbSBhbmQgbiAoMSAmbGU7IG0sIG4gJmxlOyAzMCksIGluZGljYXRpbmcgdGhlIHNpemUgb2YgYm9hcmQuVGhlIG5leHQgbSBsaW5lcyBkZXNjcmliZSB0aGUgaW5pdGlhbCBzZXR0aW5nIG9mIHRoZSBib2FyZC4gRWFjaCBsaW5lIGNvbnRhaW5zIG4gY2hhcmFjdGVycywgZWl0aGVyICZsc3F1bzsqJnJzcXVvOyBvciAmbHNxdW87LiZyc3F1bzssIGluZGljYXRpbmcgaWYgdGhlIGNvcnJlc3BvbmRpbmcgc3F1YXJlIGlzIGFuIG9ic3RhY2xlIG9yIGVtcHR5LCByZXNwZWN0aXZlbHkuIFtGb3IgZXhhbXBsZSwgc2VlIGJlbG93IGZvciB0aGUgaW5wdXQgZmlsZSBjb3JyZXNwb25kaW5nIHRvIHRoZSBjYXNlIGluIHRoZSBmaWd1cmUgYWJvdmUuXSBJdCBpcyBndWFyYW50ZWVkIHRoYXQgdGhlIGluaXRpYWwgYm9hcmQgaXMgbm90IGZ1bGx5IGNvdmVyZWQgYnkgb2JzdGFjbGVzLiBQcm9jZXNzIHVudGlsIGVuZC1vZi1maWxlOyB0aGVyZSBpcyBubyBlbmQgb2YgZGF0YSBmbGFnLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3RlcHMgdG8gY292ZXIgdGhlIGJvYXJkLiBGb2xsb3cgdGhlIGZvcm1hdCBleGFjdGx5OiAmbGRxdW87Q2FzZSZyZHF1bzssIG9uZSBzcGFjZSwgdGhlIGNhc2UgbnVtYmVyLCBhIGNvbG9uIGFuZCBvbmUgc3BhY2UsIGFuZCBvbmUgaW50ZWdlciBpbmRpY2F0aW5nIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdGVwcyB0byB3aW4gdGhlIGdhbWUsIG9yIGlmIHRoZXJlIGlzIG5vIHdheSB0byB3aW4sIHRoZSBudW1iZXIgLTEuIERvIG5vdCBwcmludCBhbnkgdHJhaWxpbmcgc3BhY2VzPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

시간 제한 안내

아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.

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