Problem 5 - Collapse
Introduction
Collapse is a game in which the player is shown a grid of colored
blocks. The player can attempt to remove blocks by selecting one.
If the block the player selected is part of 4 or more adjacent
blocks of the same color, those blocks are removed. The adjacent blocks
needn't be in a straight line but they must be 4-connected
(connected by moving left, right, up, or down)
to the selected block using only blocks of the same color. Any blocks above
the ones removed fall down to fill the empty space. If a column becomes
empty the columns are shifted in from the sides to fill the empty space.
Empty columns on the right half of the board are filled by shifting
the columns to the right of the empty column left;
those on the left are filled by shifting from the left.
Input
The input will consist of one line containing the number of rows followed
by the number of columns separated by a space with no other spaces on
the line. The number of columns will be even. Both numbers will be positive.
The second line will contain a row number
and a column number (separated by a single space) representing the
position of the block the player is trying to remove. That position
is guaranteed to be valid but the block there may not
be part of 4 or more adjacent blocks of the same color and may
even be empty. The top row
is row 0; the highest numbered row is at the bottom. The left column
is column 0; the highest numbered column is on the right.
The rest of the input will consist of one line per row
with each line containing exactly one character per column. The
characters will be digits (representing colors)
or periods ('.') to represent empty spaces.
The input will represent a legal situation in the game -- all
empty columns will be on the sides and no block will
be above an empty space.
Output
The output must consist of a representation of the game board in the
same format as that given for the input after the selected block and
its neighbors of the same color have been removed if appropriate according
to the rules of the game.
Example
Input:
7 6
5 1
.1....
.2....
.4.3..
.3.12.
21.42.
11.43.
111544
The player has selected the second 1 in the next-to-last row.
The six 1's in the
lower left corner are then removed to yield the output configuration.
Output:
......
......
...3..
..112.
..242.
..443.
.23544