DWITE Online Computer Programming Contest, February 2009, Problem 4

Tasked with connecting all of the computers in a room together, you want to save 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 will contain 5 sets of input, each a ~10 \times 10~ map – a layout of the room. Periods . for empty space, Pound signs # for computer nodes. There are no obstacles, but the wiring can only go in up/down left/right lines, not diagonally. The distance between two adjacent cells is 1. There will be ~2 \le n \le 20~ nodes.

The output will contain 5 lines, each an integer sum of the minimum cable distance required for a 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).

Sample Input

..........
..........
..........
..........
...#...#..
..........
..........
..........
..........
..........
#........#
..........
..........
..........
..........
..........
..........
..........
..........
#........#

Sample Output

8
36

Problem Resource: DWITE