Kattis

Shovelling Snow

Note that this is an easier version of the problem shovelling.

Anna, Bengt, Christian and Diana are four good friends living in a slightly desolate place called Sweden just north of Denmark. These four friends like to visit each other as often as possible. During the summers, going from any of the four friends’ houses to another is an easy task. However, in the winter this can get pretty cumbersome because of the significant amount of snow that persists in clogging up the ground. So in order to visit each other in the winter, the four friends have to plow the roads between each others houses. Your job is to help them find the best way to do this.

We model the map of Sweden as a rectangular grid, where each grid square is either one of the four friends’ houses, an obstacle (e.g. another house or a tree), or ground. Some of the ground may already be cleared of snow by the local authorities, while other parts of the ground may be snow-covered. It is possible to get from one point to another if there is a path between them (using only vertical and horizontal moves) which only passes through grid squares containing clear ground or grid squares containing one of the four friends’ houses.

Now, the four friends want to plow the snow from some of the snow-covered squares such that from each of the four friends’ houses it is possible to get to any of the other three houses. Being good friends, the four friends all help out doing equal parts in the exerting task of shovelling the snow, but being notoriously lazy, they want to put in as little effort as possible. In other words, the four friends want the total amount of snow to plow (measured as the number of snow-covered squares to clear) to be as small as possible.

Figure 1 shows an example of an input and an optimal solution.

oooooooo       oooooooo
oooooooB       ooo....B
oo#o####       oo#.####
Co#ooooo       Co#.oooo
oo#ooDoo       .o#..Doo
oooooooo       ....oooo
ooAooooo       ooAooooo
oooooooo       oooooooo

Figure 1: The map before plowing is on the left side and a possible optimal solution of cost 13 on the right side. $A, B, C, D$ denote the houses of Anna, Bengt, Christian and Diana and # is an obstacle.

Input

The input consists of several test cases (at most $50$), each separated by a blank line. The first line of each test case contains two integers $n$ and $m$, both between $1$ and $20$ (inclusive), indicating the width and the height of the map, respectively. Then follow $m$ lines, each containing $n$ characters (excluding the $\backslash$n’ end-of-line character), representing the map. The symbols that can occur in a map are:

 A Anna’s home B Bengt’s home C Christian’s home D Diana’s home o Snow-covered ground . Cleared ground # An obstacle

You may assume that each test case contains each of Anna’s, Bengt’s, Christian’s and Diana’s homes exactly once. The input is terminated by a test case where $n = 0$ and $m = 0$.

Output

For each test case output one line containing the minimal number of squares that need to be cleared from snow.

Sample Input 1 Sample Output 1
8 8
oooooooo
oooooooB
oo#o####
Co#ooooo
oo#ooDoo
oooooooo
ooAooooo
oooooooo

8 8
oooooooo
...ooooB
oo#o####
Co#ooooo
oo#ooDoo
oooooooo
ooAooooo
oooooooo

0 0

13
11