시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB354437194447819.252%

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

예제 입력 1

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

예제 출력 1

3

예제 입력 2

4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

예제 출력 2

2

예제 입력 3

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

예제 출력 3

2
W3sicHJvYmxlbV9pZCI6IjMxOTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzFcdWM4NzBcdWM3NTggXHVkNjM4XHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0NTAgXHViOWM4XHViOWFjXHVjNzU4IFx1YmMzMVx1Yzg3MFx1YWMwMCBcdWQ2MzhcdWMyMThcdWM1ZDBcdWMxMWMgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVhZGY4XHViODA3XHVjOWMwXHViOWNjIFx1YjQ1MCBcdWI5YzhcdWI5YWNcdWIyOTQgXHVkNjM4XHVjMjE4XHViOTdjIFx1YjM2ZVx1YWNlMCBcdWM3ODhcdWIyOTQgXHViZTU5XHVkMzEwXHVjNzNjXHViODVjIFx1YjljY1x1YjA5OFx1YzljMCBcdWJhYmJcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYzOFx1YzIxOFx1YjI5NCBcdWQ1ODlcdWM3NzQgUlx1YWMxYywgXHVjNWY0XHVjNzc0IENcdWFjMWNcdWM3NzggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YmFhOFx1YzU5MVx1Yzc3NFx1YjJlNC4gXHVjNWI0XHViNWE0IFx1Y2U3OFx1Yzc0MCBcdWM1YmNcdWM3NGNcdWM3M2NcdWI4NWMgXHViMzZlXHVjNWVjXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MzhcdWMyMThcdWIyOTQgXHVjYzI4XHViODQwXHViODVjIFx1YjE3OVx1YjI5NFx1YjM3MCwgXHViOWU0XHVjNzdjIFx1YmIzYyBcdWFjZjVcdWFjMDRcdWFjZmMgXHVjODExXHVjZDA5XHVkNTVjIFx1YmFhOFx1YjRlMCBcdWJlNTlcdWQzMTAgXHVhY2Y1XHVhYzA0XHVjNzQwIFx1YjE3OVx1YjI5NFx1YjJlNC4gXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWFjZjVcdWFjMDRcdWM3NzQgXHVjODExXHVjZDA5XHVkNTU4XHViODI0XHViYTc0IFx1YWMwMFx1Yjg1Y1x1YjA5OCBcdWMxMzhcdWI4NWNcdWI4NWMgXHViMmZmXHVjNTQ0IFx1Yzc4OFx1YjI5NCBcdWFjODNcdWI5Y2MgKFx1YjMwMFx1YWMwMVx1YzEyMFx1Yzc0MCBcdWFjZTBcdWI4MjRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KSBcdWMwZGRcdWFjMDFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OFx1YzVkMFx1YjI5NCBcdWMxMzggXHVhYzAwXHVjOWMwIFx1YzYwOFx1YWMwMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uLlhYWFhYWC4uWFguWFhYIC4uLi5YWFhYLi4uLi4uLlhYIC4uLi4uWFguLi4uLi4uLi4uIFxyXG4uLi4uWFhYWFhYWFhYLlhYWCAuLi4uLlhYWFguLlguLi4uLiAuLi4uLi5YLi4uLi4uLi4uLiBcclxuLi4uWFhYWFhYWFhYWFhYLi4gLi4uLlhYWC4uWFhYWC4uLi4gLi4uLi5YLi4uLi5YLi4uLi4gXHJcbi4uWFhYWFguLlhYWFhYWC4uIC4uLlhYWC4uLi5YWFhYLi4uIC4uLi5YLi4uLi4uWFguLi4uIFxyXG4uWFhYWFhYLi5YWFhYWFguLiAuLlhYWFguLi4uWFhYWC4uLiAuLi5YWC4uLi4uLlhYLi4uLiBcclxuWFhYWFhYWC4uLlhYWFguLi4gLi5YWFhYLi4uLi5YWC4uLi4gLi4uLlguLi4uLi4uLi4uLi4gXHJcbi4uWFhYWFguLi5YWFguLi4uIC4uLi5YWC4uLi4uWC4uLi4uIC4uLi4uLi4uLi4uLi4uLi4uIFxyXG4uLi4uWFhYWFguWFhYLi4uLiAuLi4uLlhYLi4uLlguLi4uLiAuLi4uLi4uLi4uLi4uLi4uLiBcclxuICAgICAgXHVjYzk4XHVjNzRjICAgICAgICAgICAgICAgXHVjY2FiXHVjOWY4IFx1YjBhMCAgICAgICAgICAgICBcdWI0NThcdWM5ZjggXHViMGEwXHJcbjxcL3ByZT5cclxuXHJcbjxwPlx1YmMzMVx1Yzg3MFx1YjI5NCBcdWM2MjRcdWM5YzEgXHViYjNjIFx1YWNmNVx1YWMwNFx1YzVkMFx1YzExYyBcdWMxMzhcdWI4NWNcdWIwOTggXHVhYzAwXHViODVjXHViODVjXHViOWNjKFx1YjMwMFx1YWMwMVx1YzEyMFx1Yzc0MCBcdWM4MWNcdWM2NzhcdWQ1NWNcdWIyZTQpIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhNzBcdWNlNjBcdWM3NzQgXHVjOWMwXHViMDk4XHVjNTdjIFx1YmMzMVx1Yzg3MFx1YjRlNFx1Yzc3NCBcdWI5Y2NcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM5YzAgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTgsIDEgJmxlOyBSLCBDICZsZTsgMTUwMC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFJcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWFlMzhcdWM3NzQgQ1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTsuJiMzOTtcdWM3NDAgXHViYjNjIFx1YWNmNVx1YWMwNCwgJiMzOTtYJiMzOTtcdWIyOTQgXHViZTU5XHVkMzEwIFx1YWNmNVx1YWMwNCwgJiMzOTtMJiMzOTtcdWM3NDAgXHViYzMxXHVjODcwXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWFjMDRcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjNzhcdWI5YWNcdWIyOTQgXHViMGEwXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoibGFidWRvdmkiLCJkZXNjcmlwdGlvbiI6IjxwPlR3byBzd2FucyBhcmUgbGl2aW5nIG9uIGEgbGFrZSBidXQgdGhleSBhcmUgc2VwYXJhdGVkIHdpdGggaWNlIHRoYXQgY292ZXJzIHBhcnRzIG9mIHRoZSBsYWtlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5MYWtlIGlzIHJlY3Rhbmd1bGFyIGluIHNoYXBlIGFuZCBjb25zaXN0cyBvZiBzcXVhcmVzIGFycmFuZ2VkIGluIFIgcm93cyBhbmQgQyBjb2x1bW5zLiBTb21lIHNxdWFyZXMgYXJlIGNvdmVyZWQgd2l0aCBpY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkxha2UgaXMgZ3JhZHVhbGx5IGRlZnJvc3RpbmcgJm5kYXNoOyBpbiBvbmUgZGF5IGFsbCBvZiB0aGUgc3F1YXJlcyBjb3ZlcmVkIHdpdGggaWNlIHRoYXQgYXJlIGluIHRvdWNoIHdpdGggd2F0ZXIgbWVsdCBhbmQgdHVybiBpbnRvIHdhdGVyLiBXZSBjb25zaWRlciB0d28gc3F1YXJlcyB0byBiZSBpbiB0b3VjaCBpZiB0aGV5IGFyZSBuZWlnaGJvcnMgaG9yaXpvbnRhbGx5IG9yIHZlcnRpY2FsbHkgKGJ1dCBub3QgZGlhZ29uYWxseSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgZmlndXJlIGRlcGljdHMgdGhlIGxha2UgZnJvbSB0aGUgdGhpcmQgZXhhbXBsZTombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuLi4uWFhYWFhYLi5YWC5YWFggLi4uLlhYWFguLi4uLi4uWFggLi4uLi5YWC4uLi4uLi4uLi4gXHJcbi4uLi5YWFhYWFhYWFguWFhYIC4uLi4uWFhYWC4uWC4uLi4uIC4uLi4uLlguLi4uLi4uLi4uIFxyXG4uLi5YWFhYWFhYWFhYWFguLiAuLi4uWFhYLi5YWFhYLi4uLiAuLi4uLlguLi4uLlguLi4uLiBcclxuLi5YWFhYWC4uWFhYWFhYLi4gLi4uWFhYLi4uLlhYWFguLi4gLi4uLlguLi4uLi5YWC4uLi4gXHJcbi5YWFhYWFguLlhYWFhYWC4uIC4uWFhYWC4uLi5YWFhYLi4uIC4uLlhYLi4uLi4uWFguLi4uIFxyXG5YWFhYWFhYLi4uWFhYWC4uLiAuLlhYWFguLi4uLlhYLi4uLiAuLi4uWC4uLi4uLi4uLi4uLiBcclxuLi5YWFhYWC4uLlhYWC4uLi4gLi4uLlhYLi4uLi5YLi4uLi4gLi4uLi4uLi4uLi4uLi4uLi4gXHJcbi4uLi5YWFhYWC5YWFguLi4uIC4uLi4uWFguLi4uWC4uLi4uIC4uLi4uLi4uLi4uLi4uLi4uIFxyXG5pbiB0aGUgYmVnaW5uaW5nICAgYWZ0ZXIgZmlyc3QgZGF5ICAgYWZ0ZXIgc2Vjb25kIGRheSBcclxuPFwvcHJlPlxyXG5cclxuPHA+U3dhbnMgY2FuIG1vdmUgb25seSBvbiB3YXRlciBzcXVhcmVzIGluIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIChidXQgbm90IGRpYWdvbmFsKSBkaXJlY3Rpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIGFmdGVyIGhvdyBtYW55IGRheXMgdGhlIHN3YW5zIHdpbGwgYmUgYWJsZSB0byBtZWV0IGVhY2ggb3RoZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSIGFuZCBDLCAxICZsZTsgUiwgQyAmbGU7IDE1MDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBSIGxpbmVzIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgQyBjaGFyYWN0ZXJzLCB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIGxha2UgYXQgdGhlIGJlZ2lubmluZzogJiMzOTsuJiMzOTsgKGRvdCkgZGVub3RlcyBhIHdhdGVyIHNxdWFyZSwgJiMzOTtYJiMzOTsgZGVub3RlcyBhbiBpY2UtY292ZXJlZCBzcXVhcmUsIGFuZCAmIzM5O0wmIzM5OyBkZW5vdGVzIGEgc3F1YXJlIHdpdGggYSBzd2FuLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgZGF5cyBmcm9tIHRoZSBwcm9ibGVtIHN0YXRlbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2005 > National Competition #2 - Seniors 2번