Problem I
Shovelling Snow
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.
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
The output should be identical to the input, with the exception that for each map some of the snow-covered squares should be transformed to clean squares, indicating which squares to clear for that map. If there is more than one optimal solution, any one will do.
| 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 |
8 8 oooooooo ooo....B oo#.#### Co#.oooo .o#..Doo ....oooo ooAooooo oooooooo 8 8 oooooooo .......B .o#.#### Co#.oooo oo#..Doo oo..oooo ooAooooo oooooooo 0 0 |
