Drops
Overview
A simple puzzle game involves removing droplets of blob from the
puzzle board. Each cell of the board has an independent amount of
blob material in it, ranging from none (0) to nearly-overflowing (4
drops). The player selectively adds drops of blob to the board, one
at time. When a nearly-overflowing (4) blob has an additional drop,
it explodes, reducing the value of that cell to 0, and propagating one
drop of blob in each of the four cardinal directions. If these
"splatters" reach the edge of the board, they disappear. If they
reach another blob, they are added to the blob, possibly causing
another explosion. The player's supply of blob drops is increased by
one for every chain-reaction (an explosion caused by splatter, not by
directly adding a drop.)
To be more formal, assume that splatter should be resolved in a
depth-first recursive fashion, resolved by splattering up, then right,
then down, then left. Before processing splatter, reduce the value of
the current cell to empty (0).
If your browser supports Flash, you can see this game in action here
Input
Input to the program is as follows. The first line is an integer
representing the number of puzzle boards to evaluate. For each board,
the next line will be two integers, r and c, which give
the number of rows and columns in the board. Then there will be
r lines of c characters each. Each character will be
either a '.' (a wall, no blobs can be placed here and no splatter can
pass through), or an integer in the range 0 .. 4, representing the
amount of blob in that cell. There will be no whitespace in the
board, except the newline at the end of the line.
Output
Output for each board is a list of the row, column coordinates that
need to have blob added to them in order to solve the puzzle with
the maximum number of drops gained (or fewest lost) at the end of
the puzzle. To differentiate among ties, these should be in
increasing lexicographic order. (That is, if we need to drop on (2,
2), (1, 1) to set up the chain, and then (1, 2) to set it off, we
should report "(1, 1) (2, 2) (1, 2)"). These should be printed
one per line, with a blank line after the output for each board.
Sample Input
1
3 6
......
.3443.
......
Sample Output
(2, 1)