시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1184 229 143 19.272%

문제

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

호수는 가로로 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..... ................. 
in the beginning   after first day   after second day 

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

몇 일이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성한다.

입력

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

각 R줄 동안 C만큼의 문자열이 주어진다.

'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

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

예제 입력 1

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

예제 출력 1

2

힌트

W3sicHJvYmxlbV9pZCI6IjMxOTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzFcdWM4NzBcdWM3NTggXHVkNjM4XHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0NTAgXHViOWM4XHViOWFjXHVjNzU4IFx1YmMzMVx1Yzg3MFx1YWMwMCZuYnNwO1x1ZDYzOFx1YzIxOFx1YzVkMFx1YzExYyBcdWMwYjRcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI4MDdcdWM5YzBcdWI5Y2MgXHViNDUwIFx1YjljOFx1YjlhY1x1YjI5NCBcdWQ2MzhcdWMyMThcdWI5N2MgXHViMzZlXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJlNTlcdWQzMTBcdWM3M2NcdWI4NWMgXHViOWNjXHViMDk4XHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjM4XHVjMjE4XHViMjk0IFx1YWMwMFx1Yjg1Y1x1Yjg1YyBSLCBcdWMxMzhcdWI4NWNcdWI4NWMgQ1x1YjljY1x1ZDA3Y1x1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzc0XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjZTc4XHVjNzQwIFx1YzViY1x1Yzc0Y1x1YzczY1x1Yjg1YyBcdWIzNmVcdWM1ZWNcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYzOFx1YzIxOFx1YjI5NCBcdWNjMjhcdWI4NDBcdWI4NWMgXHViMTc5XHViMjk0XHViMzcwLCBcdWI5ZTRcdWM3N2MmbmJzcDtcdWJiM2MgXHVhY2Y1XHVhYzA0XHVhY2ZjIFx1YzgxMVx1Y2QwOVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHViZTU5XHVkMzEwIFx1YWNmNVx1YWMwNFx1Yzc0MCBcdWIxNzlcdWIyOTRcdWIyZTQuIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVhY2Y1XHVhYzA0XHVjNzc0IFx1YzgxMVx1Y2QwOVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWFjMDBcdWI4NWNcdWIwOTggXHVjMTM4XHViODVjXHViODVjIFx1YjJmZlx1YzU0NCBcdWM3ODhcdWIyOTQmbmJzcDtcdWFjODNcdWI5Y2MgKFx1YjMwMFx1YWMwMVx1YzEyMFx1Yzc0MCBcdWFjZTBcdWI4MjRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KSZuYnNwO1x1YzBkZFx1YWMwMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4XHVjNWQwXHViMjk0Jm5ic3A7XHVjMTM4IFx1YWMwMFx1YzljMCBcdWM2MDhcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4uLi5YWFhYWFguLlhYLlhYWCAuLi4uWFhYWC4uLi4uLi5YWCAuLi4uLlhYLi4uLi4uLi4uLiBcclxuLi4uLlhYWFhYWFhYWC5YWFggLi4uLi5YWFhYLi5YLi4uLi4gLi4uLi4uWC4uLi4uLi4uLi4gXHJcbi4uLlhYWFhYWFhYWFhYWC4uIC4uLi5YWFguLlhYWFguLi4uIC4uLi4uWC4uLi4uWC4uLi4uIFxyXG4uLlhYWFhYLi5YWFhYWFguLiAuLi5YWFguLi4uWFhYWC4uLiAuLi4uWC4uLi4uLlhYLi4uLiBcclxuLlhYWFhYWC4uWFhYWFhYLi4gLi5YWFhYLi4uLlhYWFguLi4gLi4uWFguLi4uLi5YWC4uLi4gXHJcblhYWFhYWFguLi5YWFhYLi4uIC4uWFhYWC4uLi4uWFguLi4uIC4uLi5YLi4uLi4uLi4uLi4uIFxyXG4uLlhYWFhYLi4uWFhYLi4uLiAuLi4uWFguLi4uLlguLi4uLiAuLi4uLi4uLi4uLi4uLi4uLiBcclxuLi4uLlhYWFhYLlhYWC4uLi4gLi4uLi5YWC4uLi5YLi4uLi4gLi4uLi4uLi4uLi4uLi4uLi4gXHJcbmluIHRoZSBiZWdpbm5pbmcgICBhZnRlciBmaXJzdCBkYXkgICBhZnRlciBzZWNvbmQgZGF5IFxyXG48XC9wcmU+XHJcblxyXG48cD5cdWJjMzFcdWM4NzBcdWIyOTQgXHVjNjI0XHVjOWMxIFx1YmIzYyBcdWFjZjVcdWFjMDRcdWM1ZDBcdWMxMWMgXHVjMTM4XHViODVjXHViMDk4IFx1YWMwMFx1Yjg1Y1x1Yjg1Y1x1YjljYyhcdWIzMDBcdWFjMDFcdWMxMjBcdWM3NDAmbmJzcDtcdWM4MWNcdWM2NzhcdWQ1NWNcdWIyZTQpIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhODcgXHVjNzdjXHVjNzc0IFx1YzljMFx1YjA5OFx1YzU3YyBcdWJjMzFcdWM4NzBcdWI0ZTRcdWM3NzQgXHViOWNjXHViMGEwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjOWMwIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCZuYnNwO1x1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBSXHVhY2ZjIENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTgsJm5ic3A7MSZuYnNwOyZsZTsgUiwgQyAmbGU7IDE1MDAuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBSXHVjOTA0IFx1YjNkOVx1YzU0OCBDXHViOWNjXHVkMDdjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiYjMzk7LiYjMzk7XHVjNzQwIFx1YmIzYyBcdWFjZjVcdWFjMDQsICYjMzk7WCYjMzk7XHViMjk0IFx1YmU1OVx1ZDMxMCBcdWFjZjVcdWFjMDQsICYjMzk7TCYjMzk7XHVjNzQwIFx1YmMzMVx1Yzg3MFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2Y1XHVhYzA0XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YmIzOFx1YzgxY1x1YzVkMFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhYzc4XHViOWFjXHViMjk0IFx1YjBhMFx1Yzc0NCZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMTk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoibGFidWRvdmkiLCJkZXNjcmlwdGlvbiI6IjxwPlR3byBzd2FucyBhcmUgbGl2aW5nIG9uIGEgbGFrZSBidXQgdGhleSBhcmUgc2VwYXJhdGVkIHdpdGggaWNlIHRoYXQgY292ZXJzIHBhcnRzIG9mIHRoZSBsYWtlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5MYWtlIGlzIHJlY3Rhbmd1bGFyIGluIHNoYXBlIGFuZCBjb25zaXN0cyBvZiBzcXVhcmVzIGFycmFuZ2VkIGluIFIgcm93cyBhbmQgQyBjb2x1bW5zLiBTb21lIHNxdWFyZXMgYXJlIGNvdmVyZWQgd2l0aCBpY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkxha2UgaXMgZ3JhZHVhbGx5IGRlZnJvc3RpbmcgJm5kYXNoOyBpbiBvbmUgZGF5IGFsbCBvZiB0aGUgc3F1YXJlcyBjb3ZlcmVkIHdpdGggaWNlIHRoYXQgYXJlIGluIHRvdWNoIHdpdGggd2F0ZXIgbWVsdCBhbmQgdHVybiBpbnRvIHdhdGVyLiBXZSBjb25zaWRlciB0d28gc3F1YXJlcyB0byBiZSBpbiB0b3VjaCBpZiB0aGV5IGFyZSBuZWlnaGJvcnMgaG9yaXpvbnRhbGx5IG9yIHZlcnRpY2FsbHkgKGJ1dCBub3QgZGlhZ29uYWxseSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgZmlndXJlIGRlcGljdHMgdGhlIGxha2UgZnJvbSB0aGUgdGhpcmQgZXhhbXBsZTombmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuLi4uWFhYWFhYLi5YWC5YWFggLi4uLlhYWFguLi4uLi4uWFggLi4uLi5YWC4uLi4uLi4uLi4gXHJcbi4uLi5YWFhYWFhYWFguWFhYIC4uLi4uWFhYWC4uWC4uLi4uIC4uLi4uLlguLi4uLi4uLi4uIFxyXG4uLi5YWFhYWFhYWFhYWFguLiAuLi4uWFhYLi5YWFhYLi4uLiAuLi4uLlguLi4uLlguLi4uLiBcclxuLi5YWFhYWC4uWFhYWFhYLi4gLi4uWFhYLi4uLlhYWFguLi4gLi4uLlguLi4uLi5YWC4uLi4gXHJcbi5YWFhYWFguLlhYWFhYWC4uIC4uWFhYWC4uLi5YWFhYLi4uIC4uLlhYLi4uLi4uWFguLi4uIFxyXG5YWFhYWFhYLi4uWFhYWC4uLiAuLlhYWFguLi4uLlhYLi4uLiAuLi4uWC4uLi4uLi4uLi4uLiBcclxuLi5YWFhYWC4uLlhYWC4uLi4gLi4uLlhYLi4uLi5YLi4uLi4gLi4uLi4uLi4uLi4uLi4uLi4gXHJcbi4uLi5YWFhYWC5YWFguLi4uIC4uLi4uWFguLi4uWC4uLi4uIC4uLi4uLi4uLi4uLi4uLi4uIFxyXG5pbiB0aGUgYmVnaW5uaW5nICAgYWZ0ZXIgZmlyc3QgZGF5ICAgYWZ0ZXIgc2Vjb25kIGRheSBcclxuPFwvcHJlPlxyXG5cclxuPHA+U3dhbnMgY2FuIG1vdmUgb25seSBvbiB3YXRlciBzcXVhcmVzIGluIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIChidXQgbm90IGRpYWdvbmFsKSBkaXJlY3Rpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgY2FsY3VsYXRlIGFmdGVyIGhvdyBtYW55IGRheXMgdGhlIHN3YW5zIHdpbGwgYmUgYWJsZSB0byBtZWV0IGVhY2ggb3RoZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5GaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSIGFuZCBDLCAxICZsZTsgUiwgQyAmbGU7IDE1MDAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBSIGxpbmVzIGNvbnRhaW5zIGEgc2VxdWVuY2Ugb2YgQyBjaGFyYWN0ZXJzLCB0aGUgZGVzY3JpcHRpb24gb2YgdGhlIGxha2UgYXQgdGhlIGJlZ2lubmluZzogJiMzOTsuJiMzOTsgKGRvdCkgZGVub3RlcyBhIHdhdGVyIHNxdWFyZSwgJiMzOTtYJiMzOTsgZGVub3RlcyBhbiBpY2UtY292ZXJlZCBzcXVhcmUsIGFuZCAmIzM5O0wmIzM5OyBkZW5vdGVzIGEgc3F1YXJlIHdpdGggYSBzd2FuLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgZGF5cyBmcm9tIHRoZSBwcm9ibGVtIHN0YXRlbWVudC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=