A vertical cross-section of a bin is an R by C grid. Each cell is empty air (.), a fixed rock (#), or a sand grain (o). Gravity pulls every sand grain straight down within its own column: a grain falls until it rests on the floor (the bottom row), on a rock, or on another grain that has already settled. Rocks never move, and sand never moves sideways. Apply gravity until nothing else can fall, then report the grid. Row 0 is the top.
Line 1: two integers R and C.
Next R lines: each a string of C characters, each ., #, or o.
Print R lines, the settled grid in the same character encoding.
Example 1
Input
3 3 o.o ... ..#
Expected
... ..o o.#
Explanation
The grain in column 0 falls to the bottom row; the grain in column 2 rests just above the rock in the last row.
Example 2
Input
2 2 oo oo
Expected
oo oo
Explanation
Every column is already packed with grains resting on the floor, so nothing moves.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →