Bacon Graph

Completed July 17, 2010

New Graph City, a bustling metropolis, is planning on adding some new bacon dispensers to serve the residents. You see, the citizens of NGC have developed an insatiable addiction to bacon as part of a government plot to control the population with delicious breakfast foods.

You are the overworked and cruely under-baconed city planner. The powers that be have called upon you to select the optimal street corners for each dispenser.

Given an n by m graph of the city that shows the locations of the p largest population centers of the city, you need to decide where each of b dispensers should be placed so that the total distance between each population center and its closest bacon-dispenulator is the shortest.

The two rules are that you can't place a dispenser on the same graph location as a population center, and that distance should be calculated using Taxicab Geometry rather than straight Euclidean distance. (tldr: residents are only able to move vertically and horizontally along the graph, never diagonally.)

Example

A 8×8 graph containing 6 population centers, with 3 bacon dispensers to deploy.

Example Probem

Given this graph, you might select the following locations for the bacon deployment. If we calulate the distance for each population center, we get a shortest possible total distance of 10, because 3+2+2+1+1+1 = 10.

Example Solution

Instructions

Write a program that is able to solve the following sample graphs, along with any similar graph given a n by m graph with p population centers and b bacon dispensers available.

The first line of the data format is "nxm b", where n is width, m is height and b is the bacon dispensers available to you. The following lines are a representation of the graph where P represents a population center and a period (.) represents an empty space where dispensers may be deployed.

You may download more samples here, along with a python script to generate more.

Small Sample

8x8 3
........
........
....PP..
........
...P....
........
.PP.P...
........

Medium Sample

16x16 5
...........P....
...........P....
..............PP
................
................
................
................
................
...............P
.P..............
....P...........
................
..P.............
................
........P.......
...........P....

Large Sample

32x32 10
.....................P..........
.......P...........P............
.........................P......
................................
................................
.P.................P............
.................P..............
................................
................................
...................P............
................................
.PP.............................
................................
................................
................................
................................
.......P..P.....................
................................
................................
................................
....P...........................
..............P....P............
..........P...........P.........
................................
................................
.......P.......................P
................P...............
................................
................................
................................
................................
................................
### Output

Your program should output the combined shortest distance of all of the population centers. Additionally, it should output X Y coordinates of each of the bacon dispenulators.

Good luck!

Thanks Chronicler for pointing out an error in the original example!

This challenge is now closed.


Scoreboard

None yet!

Come Chat!

Join channel ##proggit on freenode.

Bugs

Having issues with the the site? Let us know.