2128. Let the Sand Settle

A grid holds three kinds of cell:

o a grain of sand . empty space # a solid block, which never moves

Gravity pulls every grain straight down, within its own column, until it rests on the floor, on a block, or on another grain. Sand never moves sideways. Print the settled grid.

.o. ... ... -> ... ... .o.

o.o ... .#. -> .#. o.o o.o ... o.o

In the second example the left column has two grains that stack at the bottom, and the right column is the same; the block in the middle column is not in either falling path.

## What most people try first

Repeat a pass over the whole grid moving every grain down one square, until a pass changes nothing. That is correct, and it is O(r) passes of O(r c) work, so O(r^2 c): at 1000 by 1000 that is 10^9 cell visits.

It is worth writing once, because it is also the easiest thing to be sure of, and the reference oracle uses exactly it to check the fast method.

## Each column is independent, so sweep it once

Sand never moves sideways, so the columns do not interact at all and each can be settled on its own. Walk a column from the BOTTOM upwards, keeping a pointer to the lowest free cell:

for each column: write = bottom row for row from bottom to top: if the cell is '#': write = row - 1 nothing falls past a block if the cell is 'o': clear it, put 'o' at write, write = write - 1

One pass per column, so O(r c) in total.

## Why the sweep must go upwards

Going downwards means a grain can be moved into a cell that a later step then examines again, so one grain falls repeatedly in a single pass and overtakes grains below it. Sweeping upwards, every cell is read exactly once and the write pointer only ever moves up, so each grain is placed once and never revisited.

That is the same discipline as problem 2127, where cells had to be read from the previous generation. Here it is achieved by the direction of the sweep rather than by a second grid.

## The block resets the pointer

When the sweep meets #, the lowest free cell becomes the row ABOVE it, not the bottom of the grid. Forgetting that lets sand fall through solid blocks, which the declared test with a block between two grains catches.

## Cost

O(r c), one pass per column, with O(1) extra memory beyond the grid itself.

Constraints - `1 ≤ r, c ≤ 1000` - every character is `o`, `.` or `#` - sand falls straight down only and never moves sideways - blocks never move