Anna, Boris, 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 winters, the four friends have to clear up 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 clear away 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 in this job as possible. In other words, the four friends want the total amount of snow to clear away (measured as the number of snow-covered squares to clear) to be as small as possible. Input The input consists of several test cases, 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 ‘\n’ end-of-line character), representing the map. The symbols that can occur in a map are: A - Anna’s home B - Bori’s home C - Christian’s home D - Diana’s home o - Snow-covered ground . - Cleared ground
You may assume that each test case contains each of Anna’s, Boris’, 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 88 oooooooo oooooooB oo#o####
2/2 Co#ooooo oo#ooDoo oooooooo ooAooooo oooooooo 88 oooooooo ...ooooB oo#o#### Co#ooooo oo#ooDoo oooooooo ooAooooo oooooooo 00 Sample Output 88 oooooooo ooo....B oo#.#### Co#.oooo .o#..Doo ....oooo ooAooooo oooooooo 88 oooooooo .......B .o#.#### Co#.oooo oo#..Doo oo..oooo ooAooooo oooooooo 00