JMU F17 Week 7

Start

2017-10-16 23:00 CEST

JMU F17 Week 7

End

2017-10-23 23:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -59 days 11:14:33

Time elapsed

168:00:00

Time remaining

0:00:00

Problem C
Falling Apples

/problems/apples/file/statement/en/img-0001.png
You have a 2D rectangular grid. Each grid cell contains either an apple, an obstacle, or is empty. Empty cells are denoted as ’.’, apples as ’a’, and obstacles as ’#’. You are to implement a simulation of gravity, based on the following rules:
  • The obstacles do not move.

  • Whenever there is an empty cell immediately below an apple, the apple moves into the empty cell.

Print out the final configuration of the board after all apples reach their final locations. Merely iterating the gravity rule, a step at a time, will likely take too long on large datasets.

Input

The input begins with a line containing integers $R$ and $C$, designating the number of rows and columns of the grid, such that $1 \leq R \leq 50\, 000$ and $1 \leq C \leq 10$. The first line is followed by $R$ additional lines, each designating a row of the grid, from top to bottom. Each line has $C$ characters, each of which is either ’.’, ’a’, or ’#’.

Output

Output $R$ grid lines displaying the final state.

Sample Input 1 Sample Output 1
3 3
aaa
#..
..#
a..
#.a
.a#
Sample Input 2 Sample Output 2
4 5
aaa.a
aa.a.
a.a..
...a.
.....
a....
aaaa.
aaaaa