## 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.

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.

### 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 "**n**x**m** **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.