DWITE Online Computer Programming Contest
February 2009
Problem 4
Wiring the Server Room

Tasked with connecting all of the computers in a room together, you want to save money on the wires and figure out the optimal plan of action. The computers are stationary and each has two network ports. For the sake of redundancy, all of the ports must be used. You are essentially making a loop through the points on a map.

The input file DATA4.txt will contain 5 sets of input, each a 10x10 map -- the layout of the room. Periods (.) denote empty space and pound signs (#) denote computer nodes (ports). There are no obstacles, but the wiring can only go in up/down/left/right steps, not diagonally. The distance between two adjacent cells is 1. There will be 2 <= n <= 20 nodes.

The output file OUT4.txt will contain 5 lines, each being an integer sum of the minimum cable distance required for the setup.

Note: A case with only 2 nodes still requires 2 wires.

Another note: Wires could run under each other and computer nodes (without connecting to them).

Warning: You might not necessary be able to solve all of the larger test cases in the limited execution time, so remember to write your solutions as they become available. There will be plenty of cases below the maximum, and they will be spread out in a gradient from low to high.

Sample Input (first two shown):
..........
..........
..........
..........
...#...#..
..........
..........
..........
..........
..........
#........#
..........
..........
..........
..........
..........
..........
..........
..........
#........#
		        
Sample Output (first two shown):
8
36
		        

Explanation for the wiring in the above cases:

..........     #--------#
..........     |........|
..........     |........|
..........     |........|
...#===#..     |........|
..........     |........|
..........     |........|
..........     |........|
..........     |........|
..........     #--------#