2175. Particles That Vanish Where They Meet

An r by c grid holds n particles, each on its own cell and each heading in one of four directions, given as 0 for north, 1 for east, 2 for south and 3 for west. North decreases the row. The walls reflect.

Every particle moves at the same instant. One tick, in order:

1. each surviving particle checks the cell it is heading into. If that cell is outside the grid, the particle REVERSES first, so north becomes south and east becomes west. 2. each particle then moves one cell in the direction it now faces. 3. any cell now holding TWO OR MORE particles loses all of them. They vanish together and take no further part.

After exactly t ticks, print the grid as r lines of c characters, with # on a cell holding a surviving particle and . everywhere else.

``` r = 3, c = 3, t = 1, one particle at (0,0) heading south and one at (2,0) heading north

both move into cell (1,0) on the same tick, so both vanish. -> ... ... ... ```

``` r = 3, c = 3, t = 4, one particle at (0,0) heading south

it goes to (1,0), (2,0), then reverses at the wall and goes to (1,0) and (0,0). Nothing to collide with, so it is back where it started. -> #.. ... ... ```

## What most people try first

Walking the particles one at a time and writing each into the grid as it moves. That makes the answer depend on the order you happened to walk them: a particle moved early can be seen by a particle moved later, and the collision rule then fires at the wrong moment or not at all. The statement says every particle moves at the SAME instant, so no particle may ever see another one's new position while deciding its own.

The shape that cannot get this wrong is to read only from the old state and write only to a new one:

for each tick: new = [] for each particle: reverse if it must, then step, and append to new count how many particles each cell of new holds keep only the particles whose cell holds exactly one

The counting is a separate pass over new, after every particle has moved. That is what makes the step simultaneous rather than sequential.

## Why the reflection must be decided before the move and not after

A particle on the bottom row heading south would leave the grid. Reversing first means it moves north on that tick, so it is never outside the grid at any point. Letting it step out and then pulling it back would place it two cells from where the rule says, and on a grid of three rows that is the difference between the second worked example returning to (0,0) and never returning at all.

Note that a particle on the bottom row heading south and one on the row above heading north SWAP cells rather than meeting, so neither vanishes. The rule asks only about cells holding two or more particles after the move, so a swap is not a collision here. That is a decision, and it is made in the statement rather than left to the implementation.

## Why three or more can share a cell

Unlike a line, a grid cell can be entered from four sides, so three or even four particles can arrive together. The rule says all of them vanish, which is why the step counts particles per cell rather than pairing them up.

## Overflow

Everything here is small. The grid is at most 50 by 50, there are at most 50 particles, and t is at most 200, so at most 10000 moves happen in total. Every value fits in a 32 bit integer with room to spare, and no test is tagged as an overflow because none could be.

## Cost

O(t * (n + r * c)) time and O(n + r * c) memory.

Constraints - `2 ≤ r, c ≤ 50` - `1 ≤ n ≤ 50` - `0 ≤ t ≤ 200` - `0 ≤ row < r` and `0 ≤ column < c`, and the starting cells are distinct - each direction is 0, 1, 2 or 3 - every particle moves at the same instant - a particle heading out of the grid reverses before moving, so it is never outside the grid - two particles that swap cells do not collide; only a cell holding two or more after the move loses them