시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB52482183581255533.074%

문제

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

티떱숲의 지도는 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+XHViOWU0IFx1YmQ4NFx1YjljOFx1YjJlNCBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWIyOTQgXHVkNjA0XHVjN2FjIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWFjZmMgXHVjNzc4XHVjODExXHVkNTVjIFx1YjEyNCBcdWNlNzggXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gKFx1YzcwNCwgXHVjNTQ0XHViNzk4LCBcdWM2MjRcdWI5NzhcdWNhYmQsIFx1YzY3Y1x1Y2FiZCkgXHViYjNjXHViM2M0IFx1YjllNCBcdWJkODRcdWI5YzhcdWIyZTQgXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1Y2U3OFx1YzczY1x1Yjg1YyBcdWQ2NTVcdWM3YTVcdWQ1NWNcdWIyZTQuIFx1YmIzY1x1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVhY2ZjIFx1Yzc3OFx1YzgxMVx1ZDU3NFx1Yzc4OFx1YjI5NCBcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjZTc4KFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NWMgXHViY2MwXHVjNzQ0IFx1YWNmNVx1YzcyMClcdWM3NDAgXHViYjNjXHVjNzc0IFx1Y2MyOFx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YmIzY1x1YWNmYyBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWIyOTQgXHViM2NjXHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1YjI5NCBcdWJiM2NcdWI4NWMgXHVjYzI4XHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzVlZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YWNlMCwgXHViYjNjXHViM2M0IFx1YmU0NFx1YmM4NFx1Yzc1OCBcdWMxOGNcdWFkNzRcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDJmMFx1YjViMVx1YzIzMlx1Yzc1OCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhY2UwXHVjMmI0XHViM2M0XHVjZTU4XHVhYzAwIFx1YzU0OFx1YzgwNFx1ZDU1OFx1YWM4YyBcdWJlNDRcdWJjODRcdWM3NTggXHVhZDc0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWMyZGNcdWFjMDRcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1YjI5NCBcdWJiM2NcdWM3NzQgXHVjYzMwIFx1YzYwOFx1YzgxNVx1Yzc3OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHViMmU0XHVjNzRjIFx1YzJkY1x1YWMwNFx1YzVkMCBcdWJiM2NcdWM3NzQgXHVjYzMwIFx1YzYwOFx1YzgxNVx1Yzc3OCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVhY2UwXHVjMmI0XHViM2M0XHVjZTU4XHViMjk0IFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3NCBcdWFjZTBcdWMyYjRcdWIzYzRcdWNlNThcdWFjMDAgXHViYjNjXHVjNWQwIFx1YmU2MFx1YzljMFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuIDxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCA1MFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgUlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMmYwXHViNWIxXHVjMjMyXHVjNzU4IFx1YzljMFx1YjNjNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWMgXHViYjM4XHVjNzkwXHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTtEJiMzOTtcdWM2NDAgJiMzOTtTJiMzOTtcdWIyOTQgXHVkNTU4XHViMDk4XHVjNTI5XHViOWNjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWNlMFx1YzJiNFx1YjNjNFx1Y2U1OFx1YWMwMCBcdWJlNDRcdWJjODRcdWM3NTggXHVhZDc0XHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgXHViZTQ0XHViYzg0XHVjNzU4IFx1YWQ3NFx1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNFx1YmE3NCwgJnF1b3Q7S0FLVFVTJnF1b3Q7XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMDU1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU0xJS0FSIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgZXZpbCBlbXBlcm9yIENhY3R1cyBoYXMgaW4gaGlzIHBvc3Nlc3Npb24gdGhlIE1hZ2ljIEtlZyBhbmQgaGFzIGZsb29kZWQgdGhlIEVuY2hhbnRlZCBGb3Jlc3QhIFRoZSBQYWludGVyIGFuZCB0aGUgdGhyZWUgbGl0dGxlIGhlZGdlaG9ncyBub3cgaGF2ZSB0byByZXR1cm4gdG8gdGhlIEJlYXZlciYjMzk7cyBkZW4gd2hlcmUgdGhleSB3aWxsIGJlIHNhZmUgZnJvbSB0aGUgd2F0ZXIgYXMgcXVpY2tseSBhcyBwb3NzaWJsZSEmbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIG1hcCBvZiB0aGUgRW5jaGFudGVkIEZvcmVzdCBjb25zaXN0cyBvZiBSIHJvd3MgYW5kIEMgY29sdW1ucy4gRW1wdHkgZmllbGRzIGFyZSByZXByZXNlbnRlZCBieSAmIzM5Oy4mIzM5OyBjaGFyYWN0ZXJzLCBmbG9vZGVkIGZpZWxkcyBieSAmIzM5OyomIzM5OyBhbmQgcm9ja3MgYnkgJiMzOTtYJiMzOTsuIEFkZGl0aW9uYWxseSwgdGhlIEJlYXZlciYjMzk7cyBkZW4gaXMgcmVwcmVzZW50ZWQgYnkgJiMzOTtEJiMzOTsgYW5kIHRoZSBQYWludGVyIGFuZCB0aGUgdGhyZWUgbGl0dGxlIGhlZGdlaG9ncyBhcmUgc2hvd24gYXMgJiMzOTtTJiMzOTsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkV2ZXJ5IG1pbnV0ZSB0aGUgUGFpbnRlciBhbmQgdGhlIHRocmVlIGxpdHRsZSBoZWRnZWhvZ3MgY2FuIG1vdmUgdG8gNCBuZWlnaGJvdXJpbmcgZmllbGRzICh1cCwgZG93biwgbGVmdCBvciByaWdodCkuIEV2ZXJ5IG1pbnV0ZSB0aGUgZmxvb2QgZXhwYW5kcyBhcyB3ZWxsIHNvIHRoYXQgYWxsIGVtcHR5IGZpZWxkcyB0aGF0IGhhdmUgYXQgbGVhc3Qgb25lIGNvbW1vbiBzaWRlIHdpdGggYSBmbG9vZGVkIGZpZWxkIGJlY29tZSBmbG9vZGVkIGFzIHdlbGwuIE5laXRoZXIgd2F0ZXIgbm9yIHRoZSBQYWludGVyIGFuZCB0aGUgdGhyZWUgbGl0dGxlIGhlZGdlaG9ncyBjYW4gcGFzcyB0aHJvdWdoIHJvY2tzLiBOYXR1cmFsbHksIHRoZSBQYWludGVyIGFuZCB0aGUgdGhyZWUgbGl0dGxlIGhlZGdlaG9ncyBjYW5ub3QgcGFzcyB0aHJvdWdoIGZsb29kZWQgZmllbGRzLCBhbmQgd2F0ZXIgY2Fubm90IGZsb29kIHRoZSBCZWF2ZXImIzM5O3MgZGVuLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsLCBnaXZlbiBhIG1hcCBvZiB0aGUgRW5jaGFudGVkIEZvcmVzdCwgb3V0cHV0IHRoZSBzaG9ydGVzdCB0aW1lIG5lZWRlZCBmb3IgdGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIHRvIHNhZmVseSByZWFjaCB0aGUgQmVhdmVyJiMzOTtzIGRlbi48XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIGNhbm5vdCBtb3ZlIGludG8gYSBmaWVsZCB0aGF0IGlzIGFib3V0IHRvIGJlIGZsb29kZWQgKGluIHRoZSBzYW1lIG1pbnV0ZSkuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCB3aWxsIGNvbnRhaW4gdHdvIGludGVnZXJzLCBSIGFuZCBDLCBzbWFsbGVyIHRoYW4gb3IgZXF1YWwgdG8gNTAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgUiBsaW5lcyB3aWxsIGVhY2ggY29udGFpbiBDIGNoYXJhY3RlcnMgKCYjMzk7LiYjMzk7LCAmIzM5OyomIzM5OywgJiMzOTtYJiMzOTssICYjMzk7RCYjMzk7IG9yICYjMzk7UyYjMzk7KS4gVGhlIG1hcCB3aWxsIGNvbnRhaW4gZXhhY3RseSBvbmUgJiMzOTtEJiMzOTsgY2hhcmFjdGVyIGFuZCBleGFjdGx5IG9uZSAmIzM5O1MmIzM5OyBjaGFyYWN0ZXIuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBzaG9ydGVzdCBwb3NzaWJsZSB0aW1lIG5lZWRlZCBmb3IgdGhlIFBhaW50ZXIgYW5kIHRoZSB0aHJlZSBsaXR0bGUgaGVkZ2Vob2dzIHRvIHNhZmVseSByZWFjaCB0aGUgQmVhdmVyJiMzOTtzIGRlbi4gSWYgdGhpcyBpcyBpbXBvc3NpYmxlIG91dHB1dCB0aGUgd29yZCAmbGRxdW87S0FLVFVTJnJkcXVvOyBvbiBhIGxpbmUgYnkgaXRzZWxmLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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