1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

import sys

from collections import deque

 

r, c = map(int, sys.stdin.readline().rstrip().split())

arr = []  # board

visited = [[0] * c for _ in range(r)]  # 방문한 곳에 조상 남기는 리스트

l_list = []

water_queue = deque([])

dy = [0, 0, –1, 1]

dx = [–1, 1, 0, 0]

 

 

def main():

    for i in range(r):

        arr.append(list(sys.stdin.readline().rstrip()))

 

    for i in range(r):

        for j in range(c):

            if arr[i][j] == ‘L’:

                l_list.append((i, j))

                water_queue.append((i, j))

                continue

            if arr[i][j] == ‘.’:

                water_queue.append((i, j))

 

    print(bfs())

 

 

def bfs():

    day = 0

    l_queue = deque([l_list[0]])

 

    while True:

        n_queue = deque()

        while l_queue:

            y, x = l_queue.popleft()

            for i in range(4):

                ny = y + dy[i]

                nx = x + dx[i]

 

                if l_list[1] == (ny, nx):

                    return day

 

                if 0 <= nx < c and 0 <= ny < r and not visited[ny][nx]:

                    visited[ny][nx] = True

                    if arr[ny][nx] == ‘.’:

                        l_queue.append((ny, nx))

                    else:

                        n_queue.append((ny, nx))

 

        l_queue = n_queue

        length = len(water_queue)

        for i in range(length):

            y, x = water_queue.popleft()

            for i in range(4):

                ny = y + dy[i]

                nx = x + dx[i]

 

                if 0 <= nx < c and 0 <= ny < r and arr[ny][nx] != ‘.’:

                    water_queue.append((ny, nx))

                    arr[ny][nx] = ‘.’

        day += 1

 

 

main()