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 ’#
are to implement a simulation of gravity, based on the
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
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
|Sample Input 2
||Sample Output 2