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

import heapq

import sys

 

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

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

 

 

def dijkstra():

    q = []

 

    heapq.heappush(q, (0, (c[0][0], c[0][1]), –1))

    distance[c[0][0]][c[0][1]] = 0

    while q:

        dist, now, d = heapq.heappop(q)

        y, x = now

        if distance[y][x] < dist:

            continue

        for i in range(4):

            ny = y + dy[i]

            nx = x + dx[i]

            if not (0 <= ny < h and 0 <= nx < w) or graph[ny][nx] == ‘*’:

                continue

            plus = 0 if d == –1 or i == d else 1

            cost = dist + plus

            if cost <= distance[ny][nx]:

                distance[ny][nx] = cost

                heapq.heappush(q, (cost, (ny, nx), i))

 

 

w, h = map(int, sys.stdin.readline().rstrip().split())

graph = []

c = []

distance = [[1e9] * w for _ in range(h)]

for i in range(h):

    s = list(sys.stdin.readline().rstrip())

    for j in range(w):

        if s[j] == ‘C’:

            c.append((i, j))

    graph.append(s)

 

dijkstra()

print(distance[c[1][0]][c[1][1]] if distance[c[1][0]][c[1][1]] != 1e9 else 0)