COCI 2008/2009, Croatian Regional
Task RELJEF
Two groups of cavemen got into a land dispute and decided to settle it the old fashion-way, by throwing sticks at each other. The fight was organized in a cave, high enough that the ceiling is of no concern, but mineral deposits on the ground get in the way of flying sticks.
The cave can be divided into R rows and C columns, so that the entire cave consists of R×C cells. Each cell in the cave is either empty or contains a chunk of mineral. Two chunks of minerals are part of the same cluster if they are adjacent in one of the four main directions (up, down, left, right).
One group of cavemen is on the left side of the cave, the other on the right side. The groups alternate throwing sticks at the other group; first a group chooses the height at which the stick will fly and then (climbing on each others' shoulders as necessary) they throw it and the stick flies horizontally through the cave at the chosen height.
If the stick hits a chunk of mineral on the way, it destroys the chunk, the cell becomes empty and the stick stops its journey.
When a chunk is destroyed, it is possible that a cluster falls apart. If a newly created cluster would float in the air, then it falls down because of gravity. While falling, the cluster does not change shape i.e. all chunks in it fall together. As soon as some chunk in the falling cluster lands on a chunk from a different cluster or the ground, the entire cluster stops falling. Of course, if a cluster lands on another, they merge and become one.
Your program will be given the layout of minerals in the cave and the heights at which sticks were thrown. Determine the layout of minerals after the sticks are exchanged.
Input
The first line contains two integers R and C (1 ≤ R, C ≤ 100), the dimensions of the cave.
Each of the following R lines will contain C characters. The character '.' represents an empty cell, while the letter 'x' represents a chunk of mineral.
The next line contains an integer N (1 ≤ N ≤ 100), the number of sticks thrown.
The last line contains N integers separated by spaces, the heights at which sticks were thrown. All heights will be between 1 and R (inclusive), with height 1 being the bottom of the matrix and height R the top. The first stick is thrown left to right, the second right to left and so on.
No cluster will initially float in the air. Also, the input data will be such that at no point will two or more clusters fall simultaneously, so that there will be no ambiguous situations.
Output
The output should consist of R lines, each containing C characters, the final layout of the cave, in the same format as in the input.Examples
Sample Input5 6 Sample Output...... |
Sample Input8 8 Sample Output........ |
Sample Input7 6 Sample Output...... |
In the second example:
The first stick destroys the chunk in the fourth column at height 6, the second destroying the chunk in the seventh column of the same row.
The third stick destroys the chunk in the third column at height 4, after which the starting cluster splits in two, but both new clusters still lay on the ground.
The fourth stick destroys the chunk in the seventh column at height 3, splitting the right cluster into two. The largest cluster would float in the air and falls two cells down.
Finally, the fifth stick destroys a chunk in the second column at height 1.
All Submissions
Best Solutions
Point Value: 15
Time Limit: 1.00s
Memory Limit: 32M
Added: Apr 29, 2009
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
It's quiet in here...