시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 10164 2131 1196 19.142%

문제

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

호수는 행이 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

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

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjMxOTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzFcdWM4NzBcdWM3NTggXHVkNjM4XHVjMjE4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWI0NTAgXHViOWM4XHViOWFjXHVjNzU4IFx1YmMzMVx1Yzg3MFx1YWMwMCZuYnNwO1x1ZDYzOFx1YzIxOFx1YzVkMFx1YzExYyBcdWMwYjRcdWFjZTAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWFkZjhcdWI4MDdcdWM5YzBcdWI5Y2MgXHViNDUwIFx1YjljOFx1YjlhY1x1YjI5NCBcdWQ2MzhcdWMyMThcdWI5N2MgXHViMzZlXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWJlNTlcdWQzMTBcdWM3M2NcdWI4NWMgXHViOWNjXHViMDk4XHVjOWMwIFx1YmFiYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjM4XHVjMjE4XHViMjk0IFx1ZDU4OVx1Yzc3NCBSXHVhYzFjLCBcdWM1ZjRcdWM3NzQgQ1x1YWMxY1x1Yzc3OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViYWE4XHVjNTkxXHVjNzc0XHViMmU0LiBcdWM1YjRcdWI1YTQgXHVjZTc4XHVjNzQwIFx1YzViY1x1Yzc0Y1x1YzczY1x1Yjg1YyBcdWIzNmVcdWM1ZWNcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDYzOFx1YzIxOFx1YjI5NCBcdWNjMjhcdWI4NDBcdWI4NWMgXHViMTc5XHViMjk0XHViMzcwLCBcdWI5ZTRcdWM3N2MmbmJzcDtcdWJiM2MgXHVhY2Y1XHVhYzA0XHVhY2ZjIFx1YzgxMVx1Y2QwOVx1ZDU1YyBcdWJhYThcdWI0ZTAgXHViZTU5XHVkMzEwIFx1YWNmNVx1YWMwNFx1Yzc0MCBcdWIxNzlcdWIyOTRcdWIyZTQuIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVhY2Y1XHVhYzA0XHVjNzc0IFx1YzgxMVx1Y2QwOVx1ZDU1OFx1YjgyNFx1YmE3NCBcdWFjMDBcdWI4NWNcdWIwOTggXHVjMTM4XHViODVjXHViODVjIFx1YjJmZlx1YzU0NCBcdWM3ODhcdWIyOTQmbmJzcDtcdWFjODNcdWI5Y2MgKFx1YjMwMFx1YWMwMVx1YzEyMFx1Yzc0MCBcdWFjZTBcdWI4MjRcdWQ1NThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KSZuYnNwO1x1YzBkZFx1YWMwMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViNzk4XHVjNWQwXHViMjk0Jm5ic3A7XHVjMTM4IFx1YWMwMFx1YzljMCBcdWM2MDhcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4uLi5YWFhYWFguLlhYLlhYWCAuLi4uWFhYWC4uLi4uLi5YWCAuLi4uLlhYLi4uLi4uLi4uLiBcclxuLi4uLlhYWFhYWFhYWC5YWFggLi4uLi5YWFhYLi5YLi4uLi4gLi4uLi4uWC4uLi4uLi4uLi4gXHJcbi4uLlhYWFhYWFhYWFhYWC4uIC4uLi5YWFguLlhYWFguLi4uIC4uLi4uWC4uLi4uWC4uLi4uIFxyXG4uLlhYWFhYLi5YWFhYWFguLiAuLi5YWFguLi4uWFhYWC4uLiAuLi4uWC4uLi4uLlhYLi4uLiBcclxuLlhYWFhYWC4uWFhYWFhYLi4gLi5YWFhYLi4uLlhYWFguLi4gLi4uWFguLi4uLi5YWC4uLi4gXHJcblhYWFhYWFguLi5YWFhYLi4uIC4uWFhYWC4uLi4uWFguLi4uIC4uLi5YLi4uLi4uLi4uLi4uIFxyXG4uLlhYWFhYLi4uWFhYLi4uLiAuLi4uWFguLi4uLlguLi4uLiAuLi4uLi4uLi4uLi4uLi4uLiBcclxuLi4uLlhYWFhYLlhYWC4uLi4gLi4uLi5YWC4uLi5YLi4uLi4gLi4uLi4uLi4uLi4uLi4uLi4gXHJcbiAgICAgIFx1Y2M5OFx1Yzc0YyAgICAgICAgICAgICAgIFx1Y2NhYlx1YzlmOCBcdWIwYTAgICAgICAgICAgICAgXHViNDU4XHVjOWY4IFx1YjBhMFxyXG48XC9wcmU+XHJcblxyXG48cD5cdWJjMzFcdWM4NzBcdWIyOTQgXHVjNjI0XHVjOWMxIFx1YmIzYyBcdWFjZjVcdWFjMDRcdWM1ZDBcdWMxMWMgXHVjMTM4XHViODVjXHViMDk4IFx1YWMwMFx1Yjg1Y1x1Yjg1Y1x1YjljYyhcdWIzMDBcdWFjMDFcdWMxMjBcdWM3NDAmbmJzcDtcdWM4MWNcdWM2NzhcdWQ1NWNcdWIyZTQpIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhNzBcdWNlNjBcdWM3NzQgXHVjOWMwXHViMDk4XHVjNTdjIFx1YmMzMVx1Yzg3MFx1YjRlNFx1Yzc3NCBcdWI5Y2NcdWIwYTAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM5YzAgXHVhY2M0XHVjMGIwXHVkNTU4XHViMjk0Jm5ic3A7XHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFJcdWFjZmMgQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOCwmbmJzcDsxJm5ic3A7JmxlOyBSLCBDICZsZTsgMTUwMC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFJcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWFlMzhcdWM3NzQgQ1x1Yzc1OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsmIzM5Oy4mIzM5O1x1Yzc0MCBcdWJiM2MgXHVhY2Y1XHVhYzA0LCAmIzM5O1gmIzM5O1x1YjI5NCBcdWJlNTlcdWQzMTAgXHVhY2Y1XHVhYzA0LCAmIzM5O0wmIzM5O1x1Yzc0MCBcdWJjMzFcdWM4NzBcdWFjMDAgXHVjNzg4XHViMjk0IFx1YWNmNVx1YWMwNFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWM3OFx1YjlhY1x1YjI5NCBcdWIwYTBcdWM3NDQmbmJzcDtcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzE5NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6ImxhYnVkb3ZpIiwiZGVzY3JpcHRpb24iOiI8cD5Ud28gc3dhbnMgYXJlIGxpdmluZyBvbiBhIGxha2UgYnV0IHRoZXkgYXJlIHNlcGFyYXRlZCB3aXRoIGljZSB0aGF0IGNvdmVycyBwYXJ0cyBvZiB0aGUgbGFrZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TGFrZSBpcyByZWN0YW5ndWxhciBpbiBzaGFwZSBhbmQgY29uc2lzdHMgb2Ygc3F1YXJlcyBhcnJhbmdlZCBpbiBSIHJvd3MgYW5kIEMgY29sdW1ucy4gU29tZSBzcXVhcmVzIGFyZSBjb3ZlcmVkIHdpdGggaWNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5MYWtlIGlzIGdyYWR1YWxseSBkZWZyb3N0aW5nICZuZGFzaDsgaW4gb25lIGRheSBhbGwgb2YgdGhlIHNxdWFyZXMgY292ZXJlZCB3aXRoIGljZSB0aGF0IGFyZSBpbiB0b3VjaCB3aXRoIHdhdGVyIG1lbHQgYW5kIHR1cm4gaW50byB3YXRlci4gV2UgY29uc2lkZXIgdHdvIHNxdWFyZXMgdG8gYmUgaW4gdG91Y2ggaWYgdGhleSBhcmUgbmVpZ2hib3JzIGhvcml6b250YWxseSBvciB2ZXJ0aWNhbGx5IChidXQgbm90IGRpYWdvbmFsbHkpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIGZpZ3VyZSBkZXBpY3RzIHRoZSBsYWtlIGZyb20gdGhlIHRoaXJkIGV4YW1wbGU6Jm5ic3A7PFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uLlhYWFhYWC4uWFguWFhYIC4uLi5YWFhYLi4uLi4uLlhYIC4uLi4uWFguLi4uLi4uLi4uIFxyXG4uLi4uWFhYWFhYWFhYLlhYWCAuLi4uLlhYWFguLlguLi4uLiAuLi4uLi5YLi4uLi4uLi4uLiBcclxuLi4uWFhYWFhYWFhYWFhYLi4gLi4uLlhYWC4uWFhYWC4uLi4gLi4uLi5YLi4uLi5YLi4uLi4gXHJcbi4uWFhYWFguLlhYWFhYWC4uIC4uLlhYWC4uLi5YWFhYLi4uIC4uLi5YLi4uLi4uWFguLi4uIFxyXG4uWFhYWFhYLi5YWFhYWFguLiAuLlhYWFguLi4uWFhYWC4uLiAuLi5YWC4uLi4uLlhYLi4uLiBcclxuWFhYWFhYWC4uLlhYWFguLi4gLi5YWFhYLi4uLi5YWC4uLi4gLi4uLlguLi4uLi4uLi4uLi4gXHJcbi4uWFhYWFguLi5YWFguLi4uIC4uLi5YWC4uLi4uWC4uLi4uIC4uLi4uLi4uLi4uLi4uLi4uIFxyXG4uLi4uWFhYWFguWFhYLi4uLiAuLi4uLlhYLi4uLlguLi4uLiAuLi4uLi4uLi4uLi4uLi4uLiBcclxuaW4gdGhlIGJlZ2lubmluZyAgIGFmdGVyIGZpcnN0IGRheSAgIGFmdGVyIHNlY29uZCBkYXkgXHJcbjxcL3ByZT5cclxuXHJcbjxwPlN3YW5zIGNhbiBtb3ZlIG9ubHkgb24gd2F0ZXIgc3F1YXJlcyBpbiBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCAoYnV0IG5vdCBkaWFnb25hbCkgZGlyZWN0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGNhbGN1bGF0ZSBhZnRlciBob3cgbWFueSBkYXlzIHRoZSBzd2FucyB3aWxsIGJlIGFibGUgdG8gbWVldCBlYWNoIG90aGVyLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+Rmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgUiBhbmQgQywgMSAmbGU7IFIsIEMgJmxlOyAxNTAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgUiBsaW5lcyBjb250YWlucyBhIHNlcXVlbmNlIG9mIEMgY2hhcmFjdGVycywgdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBsYWtlIGF0IHRoZSBiZWdpbm5pbmc6ICYjMzk7LiYjMzk7IChkb3QpIGRlbm90ZXMgYSB3YXRlciBzcXVhcmUsICYjMzk7WCYjMzk7IGRlbm90ZXMgYW4gaWNlLWNvdmVyZWQgc3F1YXJlLCBhbmQgJiMzOTtMJiMzOTsgZGVub3RlcyBhIHNxdWFyZSB3aXRoIGEgc3dhbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5GaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIGRheXMgZnJvbSB0aGUgcHJvYmxlbSBzdGF0ZW1lbnQuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==