시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB444100.000%

문제

Bonnie and Clyde have noticed that parallel processing improves throughput so, instead of robbing one bank together, they’ve decided to rob two different banks simultaneously (each robbing one). They both succeeded and now they need to run to their get-away 1934 Ford Model (730 Deluxe Sedan). There are complications, of course, or the movie won’t be exciting!

The city is in the shape of a matrix with cells. Bonnie and Clyde are in two different cells, and the get-away car is in a different cell as well. Bonnie and Clyde can move in four directions: north, south, east, and west (the border cells of course have fewer move options since they cannot move across the outer walls of the city). Some cells are also blocked, i.e., neither one can move into it. To put more adventure in the movie, it is also the case that once Bonnie or Clyde moves into a cell, then neither one can move into that cell anymore, i.e., a cell is used at most once. Bonnie and Clyde cannot move into each other’s starting position either.

Given the city map (in the form of a matrix), the location for Bonnie, Clyde, and car, you are to compute the minimum total number of moves needed for both Bonnie and Clyde to get to the car, i.e., the total number of moves made by Bonnie plus the total number of moves made by Clyde.

입력

The first input line contains two integers, r and c (2 ≤ r, c ≤ 30), providing the number of rows and columns for the matrix. Each of the next r lines contains c characters, starting in column 1; this is the input matrix. There will be exactly one “B” (Bonnie’s starting location), one “C” (Clyde’s starting location), and one “F” (where the get-away Ford car is) in the input maze. The remaining cells will be “.” (empty cell – one can move into) or “x” (blocked – one cannot move into).

출력

Print the minimum total number of moves needed for both Bonnie and Clyde to get to the car. If they cannot get to the car, print -1. Note that when one reaches the car, he/she stops moving.

예제 입력 1

6 5
.....
...C.
.B.x.
.....
...F.
.....

예제 출력 1

9

예제 입력 2

3 7
.....F.
xxx.xxx
C.....B

예제 출력 2

-1

예제 입력 3

7 5
C....
...B.
xx.x.
.....
.F...
.....
.....

예제 출력 3

14

힌트

Sample Explanation: In the first sample case, Bonnie can reach the car with 4 moves and Clyde can reach the car with 5 moves, for a total of 9 moves.