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.
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 $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 |