백조의 호수

두 마리의 백조가 직사각형 호수에 살고 있다. 호수 일부는 얼음으로 덮여 있어서 처음에는 두 백조가 서로 만날 수 없다.

호수는 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은 백조가 있는 칸을 뜻한다. 백조가 있는 칸은 물로 취급한다.

두 백조가 만날 수 있게 되기까지 필요한 최소 일수를 한 줄에 출력한다.