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 10×10 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 necessarily 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.
..........
..........
..........
..........
...#...#..
..........
..........
..........
..........
..........
#........#
..........
..........
..........
..........
..........
..........
..........
..........
#........#
8
36
Explanation for the wiring in the above cases:
.......... #--------# .......... |........| .......... |........| .......... |........| ...#===#.. |........| .......... |........| .......... |........| .......... |........| .......... |........| .......... #--------#