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 file DATA4.txt will contain 5 sets of input, each a 10x10 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 <= n <= 20 nodes.
The output file OUT4.txt 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).
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 max, and they will be spread out in a gradient from low to high.
.......... .......... .......... .......... ...#...#.. .......... .......... .......... .......... .......... #........# .......... .......... .......... .......... .......... .......... .......... .......... #........#
8 36
Explanation for the wiring in the above cases:
.......... #--------# .......... |........| .......... |........| .......... |........| ...#===#.. |........| .......... |........| .......... |........| .......... |........| .......... |........| .......... #--------#