시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2140 463 200 18.957%

문제

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

호수는 가로로 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+XHJcblxyXG48cD5cdWJhNzBcdWNlNjBcdWM3NzQgXHVjOWMwXHViMDk4XHVjNTdjIFx1YmMzMVx1Yzg3MFx1YjRlNFx1Yzc3NCBcdWI5Y2NcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM5YzAgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0Jm5ic3A7XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOCwmbmJzcDsxJm5ic3A7JmxlOyBSLCBDICZsZTsgMTUwMC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFJcdWM5MDQgXHViM2Q5XHVjNTQ4IENcdWI5Y2NcdWQwN2NcdWM3NTggXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JiMzOTsuJiMzOTtcdWM3NDAgXHViYjNjIFx1YWNmNVx1YWMwNCwgJiMzOTtYJiMzOTtcdWIyOTQgXHViZTU5XHVkMzEwIFx1YWNmNVx1YWMwNCwgJiMzOTtMJiMzOTtcdWM3NDAgXHViYzMxXHVjODcwXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWFjZjVcdWFjMDRcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWFjNzhcdWI5YWNcdWIyOTQgXHViMGEwXHVjNzQ0Jm5ic3A7XHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxOTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJsYWJ1ZG92aSIsImRlc2NyaXB0aW9uIjoiPHA+VHdvIHN3YW5zIGFyZSBsaXZpbmcgb24gYSBsYWtlIGJ1dCB0aGV5IGFyZSBzZXBhcmF0ZWQgd2l0aCBpY2UgdGhhdCBjb3ZlcnMgcGFydHMgb2YgdGhlIGxha2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkxha2UgaXMgcmVjdGFuZ3VsYXIgaW4gc2hhcGUgYW5kIGNvbnNpc3RzIG9mIHNxdWFyZXMgYXJyYW5nZWQgaW4gUiByb3dzIGFuZCBDIGNvbHVtbnMuIFNvbWUgc3F1YXJlcyBhcmUgY292ZXJlZCB3aXRoIGljZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGFrZSBpcyBncmFkdWFsbHkgZGVmcm9zdGluZyAmbmRhc2g7IGluIG9uZSBkYXkgYWxsIG9mIHRoZSBzcXVhcmVzIGNvdmVyZWQgd2l0aCBpY2UgdGhhdCBhcmUgaW4gdG91Y2ggd2l0aCB3YXRlciBtZWx0IGFuZCB0dXJuIGludG8gd2F0ZXIuIFdlIGNvbnNpZGVyIHR3byBzcXVhcmVzIHRvIGJlIGluIHRvdWNoIGlmIHRoZXkgYXJlIG5laWdoYm9ycyBob3Jpem9udGFsbHkgb3IgdmVydGljYWxseSAoYnV0IG5vdCBkaWFnb25hbGx5KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBmaWd1cmUgZGVwaWN0cyB0aGUgbGFrZSBmcm9tIHRoZSB0aGlyZCBleGFtcGxlOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG4uLi5YWFhYWFguLlhYLlhYWCAuLi4uWFhYWC4uLi4uLi5YWCAuLi4uLlhYLi4uLi4uLi4uLiBcclxuLi4uLlhYWFhYWFhYWC5YWFggLi4uLi5YWFhYLi5YLi4uLi4gLi4uLi4uWC4uLi4uLi4uLi4gXHJcbi4uLlhYWFhYWFhYWFhYWC4uIC4uLi5YWFguLlhYWFguLi4uIC4uLi4uWC4uLi4uWC4uLi4uIFxyXG4uLlhYWFhYLi5YWFhYWFguLiAuLi5YWFguLi4uWFhYWC4uLiAuLi4uWC4uLi4uLlhYLi4uLiBcclxuLlhYWFhYWC4uWFhYWFhYLi4gLi5YWFhYLi4uLlhYWFguLi4gLi4uWFguLi4uLi5YWC4uLi4gXHJcblhYWFhYWFguLi5YWFhYLi4uIC4uWFhYWC4uLi4uWFguLi4uIC4uLi5YLi4uLi4uLi4uLi4uIFxyXG4uLlhYWFhYLi4uWFhYLi4uLiAuLi4uWFguLi4uLlguLi4uLiAuLi4uLi4uLi4uLi4uLi4uLiBcclxuLi4uLlhYWFhYLlhYWC4uLi4gLi4uLi5YWC4uLi5YLi4uLi4gLi4uLi4uLi4uLi4uLi4uLi4gXHJcbmluIHRoZSBiZWdpbm5pbmcgICBhZnRlciBmaXJzdCBkYXkgICBhZnRlciBzZWNvbmQgZGF5IFxyXG48XC9wcmU+XHJcblxyXG48cD5Td2FucyBjYW4gbW92ZSBvbmx5IG9uIHdhdGVyIHNxdWFyZXMgaW4gaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgKGJ1dCBub3QgZGlhZ29uYWwpIGRpcmVjdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgd2lsbCBjYWxjdWxhdGUgYWZ0ZXIgaG93IG1hbnkgZGF5cyB0aGUgc3dhbnMgd2lsbCBiZSBhYmxlIHRvIG1lZXQgZWFjaCBvdGhlci4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIFIgYW5kIEMsIDEgJmxlOyBSLCBDICZsZTsgMTUwMC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIFIgbGluZXMgY29udGFpbnMgYSBzZXF1ZW5jZSBvZiBDIGNoYXJhY3RlcnMsIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgbGFrZSBhdCB0aGUgYmVnaW5uaW5nOiAmIzM5Oy4mIzM5OyAoZG90KSBkZW5vdGVzIGEgd2F0ZXIgc3F1YXJlLCAmIzM5O1gmIzM5OyBkZW5vdGVzIGFuIGljZS1jb3ZlcmVkIHNxdWFyZSwgYW5kICYjMzk7TCYjMzk7IGRlbm90ZXMgYSBzcXVhcmUgd2l0aCBhIHN3YW4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBkYXlzIGZyb20gdGhlIHByb2JsZW0gc3RhdGVtZW50LiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==