Problem F
LumberCraft
In a variety of popular strategy games, you must harvest materials in order to build up your forces and eventually defeat your opponents (who are, of course, trying to do the same thing). Let’s play a simplified version of this kind of game. Here, a number of players (A, B, C $\ldots $) are competing to harvest as much lumber as possible.
Each player has one lumber mill marked with the player’s letter, and one lumberjack. In each turn, every player sends their lumberjack out from their mill to cut down a tree and return it to the mill. The lumberjack always chooses the tree closest to the mill. If multiple trees are equally close, the lumberjack chooses the one farthest to the east. If there is still a tie, the lumberjack chooses the southernmost.
If all goes well, each team gets to cut down one tree per turn. However, if more than one lumberjack chooses the same tree in a turn, they have to share the lumber. For example, if three lumberjacks all choose the same tree, they each get $1/3$ of the wood. Once all the trees are gone, no player can accumulate more lumber. Your job is to display the map and report how much lumber each player accumulates after a given number of turns.
Input
Input consists of up to $20$ test cases. Each test case starts with a line containing three integers, $1 \leq n \leq 100$, $1 \leq h \leq 50$ and $1 \leq w \leq 50$. The values for $h$ and $w$ give the height and width of the map. The value of $n$ is the number of turns the players have to harvest lumber. The next $h$ input lines give the initial state of the map, and each line is $w$ characters long. In the map, ! represents a tree, . represents a tree stump and the uppercase letters A through Z represent the mill locations for up to $26$ players. A line containing three zeros terminates the input.
Output
For each test case, output the state of the map after $n$ turns and the amount of lumber accumulated by each player, ordered alphabetically. For each player, output the player’s letter and then the lumber total, accurate within $0.01$ units.
| Sample Input 1 | Sample Output 1 |
|---|---|
10 10 10 !!!!!!.!!! !!!!!.B.!! !!!!!!.!!! !!!!.!!!!! !!!...!!!! .!!!.!!!!! ..!!!!!!Z! .!!!!!!!!! !A!!!!!!!. !!!!!!!!!! 0 0 0 |
!!!!!....! !!!!..B..! !!!!!....! !!!!.!..!! !!!...!!.! .!!!.!!... ..!!!!!.Z. ....!!!... .A..!!!!.. ....!!!!!! A 10.000000 B 10.000000 Z 10.000000 |
