시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 9240 2749 1871 28.417%

문제

사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다.

티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나타내어져 있다.

매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동할 수 있다. (위, 아래, 오른쪽, 왼쪽) 물도 매 분마다 비어있는 칸으로 확장한다. 물이 있는 칸과 인접해있는 비어있는 칸(적어도 한 변을 공유)은 물이 차게 된다. 물과 고슴도치는 돌을 통과할 수 없다. 또, 고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다.

티떱숲의 지도가 주어졌을 때, 고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램을 작성하시오.

고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 이동할 수 있으면 고슴도치가 물에 빠지기 때문이다. 

입력

첫째 줄에 50보다 작거나 같은 자연수 R과 C가 주어진다.

다음 R개 줄에는 티떱숲의 지도가 주어지며, 문제에서 설명한 문자만 주어진다. 'D'와 'S'는 하나씩만 주어진다.

출력

첫째 줄에 고슴도치가 비버의 굴로 이동할 수 있는 가장 빠른 시간을 출력한다. 만약, 안전하게 비버의 굴로 이동할 수 없다면, "KAKTUS"를 출력한다.

예제 입력 1

3 3
D.*
...
.S.

예제 출력 1

3

예제 입력 2

3 3
D.*
...
..S

예제 출력 2

KAKTUS

예제 입력 3

3 6
D...*.
.X.X..
....S.

예제 출력 3

6

예제 입력 4

5 4
.D.*
....
..X.
S.*.
....

예제 출력 4

4
W3sicHJvYmxlbV9pZCI6IjMwNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzhcdWNkOWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBhY1x1YzU0NVx1ZDU1YyBcdWM1NTRcdWQ3NTFcdWM3NTggXHVhZDcwXHVjOGZjIFx1Yzc3NFx1YmJmY1x1ZDYwMVx1Yzc0MCBcdWI0ZGNcdWI1MTRcdWM1YjQgXHViOWM4XHViYzk1IFx1YWQ2Y1x1YzJhY1x1Yzc0NCBcdWMxOTBcdWM1ZDAgXHViMTIzXHVjNWM4XHVhY2UwLCBcdWFkZjggXHViMmE1XHViODI1XHVjNzQ0IFx1YzJlNFx1ZDVkOFx1ZDU3NFx1YmNmNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhZGZjXHVjYzk4XHVjNzU4IFx1ZDJmMFx1YjViMVx1YzIzMlx1YzVkMCBcdWQ2NGRcdWMyMThcdWI5N2MgXHVjNzdjXHVjNzNjXHVkMGE0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzIzMlx1YzVkMFx1YjI5NCBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWFjMDAgXHVkNTVjIFx1YjljOFx1YjlhYyBcdWMwYjRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWIyOTQgXHVjODFjXHVjNzdjIFx1Y2U1Y1x1ZDU1YyBcdWNlNWNcdWFkNmNcdWM3NzggXHViZTQ0XHViYzg0XHVjNzU4IFx1YWQ3NFx1Yjg1YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViZTY4XHViOWFjIFx1YjNjNFx1YjlkZFx1YWMwMCBcdWQ2NGRcdWMyMThcdWI5N2MgXHVkNTNjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMmYwXHViNWIxXHVjMjMyXHVjNzU4IFx1YzljMFx1YjNjNFx1YjI5NCBSXHVkNTg5IENcdWM1ZjRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1YWNmM1x1Yzc0MCAmIzM5Oy4mIzM5O1x1Yjg1YyBcdWQ0NWNcdWMyZGNcdWI0MThcdWM1YjQgXHVjNzg4XHVhY2UwLCBcdWJiM2NcdWM3NzQgXHVjYzI4XHVjNzg4XHViMjk0IFx1YzljMFx1YzVlZFx1Yzc0MCAmIzM5OyomIzM5OywgXHViM2NjXHVjNzQwICYjMzk7WCYjMzk7XHViODVjIFx1ZDQ1Y1x1YzJkY1x1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1YmU0NFx1YmM4NFx1Yzc1OCBcdWFkNzRcdWM3NDAgJiMzOTtEJiMzOTtcdWI4NWMsIFx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1Yzc1OCBcdWM3MDRcdWNlNThcdWIyOTQgJiMzOTtTJiMzOTtcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWU0IFx1YmQ4NFx1YjljOFx1YjJlNCBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjEyNCBcdWNlNzggXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzcwNCwgXHVjNTQ0XHViNzk4LCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YzY3Y1x1Y2FiZCkgXHViYjNjXHViM2M0IFx1YjllNCBcdWJkODRcdWI5YzhcdWIyZTQgXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWQ2NTVcdWM3YTVcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU3NFx1Yzc4OFx1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjZTc4KFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMClcdWM3NDAgXHViYjNjXHVjNzc0IFx1Y2MyOFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YmIzY1x1YWNmYyBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWIyOTQgXHViM2NjXHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1YjI5NCBcdWJiM2NcdWI4NWMgXHVjYzI4XHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzVlZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWNlMCwgXHViYjNjXHViM2M0IFx1YmU0NFx1YmM4NFx1Yzc1OCBcdWMxOGNcdWFkNzRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDJmMFx1YjViMVx1YzIzMlx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhY2UwXHVjMmI0XHViM2M0XHVjZTU4XHVhYzAwIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWJlNDRcdWJjODRcdWM3NTggXHVhZDc0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1YjI5NCBcdWJiM2NcdWM3NzQgXHVjYzMwIFx1YzYwOFx1YzgxNVx1Yzc3OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHViMmU0XHVjNzRjIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWJiM2NcdWM3NzQgXHVjYzMwIFx1YzYwOFx1YzgxNVx1Yzc3OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhY2UwXHVjMmI0XHViM2M0XHVjZTU4XHViMjk0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWFjMDAgXHViYjNjXHVjNWQwIFx1YmU2MFx1YzljMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIDUwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4IFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQyZjBcdWI1YjFcdWMyMzJcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWJiMzhcdWM3OTBcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAmIzM5O0QmIzM5O1x1YzY0MCAmIzM5O1MmIzM5O1x1YjI5NCBcdWQ1NThcdWIwOThcdWM1MjlcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2UwXHVjMmI0XHViM2M0XHVjZTU4XHVhYzAwIFx1YmU0NFx1YmM4NFx1Yzc1OCBcdWFkNzRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YmU2MFx1Yjk3OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWJlNDRcdWJjODRcdWM3NTggXHVhZDc0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0LCAmcXVvdDtLQUtUVVMmcXVvdDtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwNTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTTElLQVIiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBldmlsIGVtcGVyb3IgQ2FjdHVzIGhhcyBpbiBoaXMgcG9zc2Vzc2lvbiB0aGUgTWFnaWMgS2VnIGFuZCBoYXMgZmxvb2RlZCB0aGUgRW5jaGFudGVkIEZvcmVzdCEgVGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIG5vdyBoYXZlIHRvIHJldHVybiB0byB0aGUgQmVhdmVyJiMzOTtzIGRlbiB3aGVyZSB0aGV5IHdpbGwgYmUgc2FmZSBmcm9tIHRoZSB3YXRlciBhcyBxdWlja2x5IGFzIHBvc3NpYmxlISZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbWFwIG9mIHRoZSBFbmNoYW50ZWQgRm9yZXN0IGNvbnNpc3RzIG9mIFIgcm93cyBhbmQgQyBjb2x1bW5zLiBFbXB0eSBmaWVsZHMgYXJlIHJlcHJlc2VudGVkIGJ5ICYjMzk7LiYjMzk7IGNoYXJhY3RlcnMsIGZsb29kZWQgZmllbGRzIGJ5ICYjMzk7KiYjMzk7IGFuZCByb2NrcyBieSAmIzM5O1gmIzM5Oy4gQWRkaXRpb25hbGx5LCB0aGUgQmVhdmVyJiMzOTtzIGRlbiBpcyByZXByZXNlbnRlZCBieSAmIzM5O0QmIzM5OyBhbmQgdGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIGFyZSBzaG93biBhcyAmIzM5O1MmIzM5Oy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RXZlcnkgbWludXRlIHRoZSBQYWludGVyIGFuZCB0aGUgdGhyZWUgbGl0dGxlIGhlZGdlaG9ncyBjYW4gbW92ZSB0byA0IG5laWdoYm91cmluZyBmaWVsZHMgKHVwLCBkb3duLCBsZWZ0IG9yIHJpZ2h0KS4gRXZlcnkgbWludXRlIHRoZSBmbG9vZCBleHBhbmRzIGFzIHdlbGwgc28gdGhhdCBhbGwgZW1wdHkgZmllbGRzIHRoYXQgaGF2ZSBhdCBsZWFzdCBvbmUgY29tbW9uIHNpZGUgd2l0aCBhIGZsb29kZWQgZmllbGQgYmVjb21lIGZsb29kZWQgYXMgd2VsbC4gTmVpdGhlciB3YXRlciBub3IgdGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIGNhbiBwYXNzIHRocm91Z2ggcm9ja3MuIE5hdHVyYWxseSwgdGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIGNhbm5vdCBwYXNzIHRocm91Z2ggZmxvb2RlZCBmaWVsZHMsIGFuZCB3YXRlciBjYW5ub3QgZmxvb2QgdGhlIEJlYXZlciYjMzk7cyBkZW4uPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwsIGdpdmVuIGEgbWFwIG9mIHRoZSBFbmNoYW50ZWQgRm9yZXN0LCBvdXRwdXQgdGhlIHNob3J0ZXN0IHRpbWUgbmVlZGVkIGZvciB0aGUgUGFpbnRlciBhbmQgdGhlIHRocmVlIGxpdHRsZSBoZWRnZWhvZ3MgdG8gc2FmZWx5IHJlYWNoIHRoZSBCZWF2ZXImIzM5O3MgZGVuLjxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgUGFpbnRlciBhbmQgdGhlIHRocmVlIGxpdHRsZSBoZWRnZWhvZ3MgY2Fubm90IG1vdmUgaW50byBhIGZpZWxkIHRoYXQgaXMgYWJvdXQgdG8gYmUgZmxvb2RlZCAoaW4gdGhlIHNhbWUgbWludXRlKS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IHdpbGwgY29udGFpbiB0d28gaW50ZWdlcnMsIFIgYW5kIEMsIHNtYWxsZXIgdGhhbiBvciBlcXVhbCB0byA1MC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBSIGxpbmVzIHdpbGwgZWFjaCBjb250YWluIEMgY2hhcmFjdGVycyAoJiMzOTsuJiMzOTssICYjMzk7KiYjMzk7LCAmIzM5O1gmIzM5OywgJiMzOTtEJiMzOTsgb3IgJiMzOTtTJiMzOTspLiBUaGUgbWFwIHdpbGwgY29udGFpbiBleGFjdGx5IG9uZSAmIzM5O0QmIzM5OyBjaGFyYWN0ZXIgYW5kIGV4YWN0bHkgb25lICYjMzk7UyYjMzk7IGNoYXJhY3Rlci4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIHNob3J0ZXN0IHBvc3NpYmxlIHRpbWUgbmVlZGVkIGZvciB0aGUgUGFpbnRlciBhbmQgdGhlIHRocmVlIGxpdHRsZSBoZWRnZWhvZ3MgdG8gc2FmZWx5IHJlYWNoIHRoZSBCZWF2ZXImIzM5O3MgZGVuLiBJZiB0aGlzIGlzIGltcG9zc2libGUgb3V0cHV0IHRoZSB3b3JkICZsZHF1bztLQUtUVVMmcmRxdW87IG9uIGEgbGluZSBieSBpdHNlbGYuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #1 4번