1526. One Step of the Colony
An R by C grid of 0 and 1 is given. Every cell has up to eight
neighbours, the cells touching it sideways, vertically or cornerwise. All cells
update SIMULTANEOUSLY by these rules, then the new grid is printed:
a 1 with fewer than 2 live neighbours -> 0
a 1 with 2 or 3 live neighbours -> 1
a 1 with more than 3 live neighbours -> 0
a 0 with exactly 3 live neighbours -> 1 otherwise stays 0
The update must happen inside the grid: apart from a constant number of scalar variables, no extra storage is allowed.
0 1 0 0 -> 0 0 0 0
0 0 1 0 1 0 1 0
1 1 1 0 0 1 1 0
0 1 0 -> 0 0 0 a vertical line of three becomes a horizontal one
0 1 0 1 1 1
0 1 0 0 0 0
1 1 0 -> 1 1 0 a block is stable
1 1 0 1 1 0
## What most people try first
Writing the new value straight into the cell. Every later neighbour count then
mixes old and new states, which is not the rule: the update is simultaneous.
The vertical line above is the smallest case that shows it. Updating in reading
order turns it into 0 0 0 / 1 1 1 / 0 1 0, because by the time the bottom row
is examined the middle row has already changed.
The honest repair is a second grid, O(R C) extra. This problem asks for
O(1).
## Two states in one integer
Each cell only ever needs two bits: what it WAS and what it BECOMES. The values are 0 and 1, so bit 0 is free to keep the old state while bit 1 records the new one.
``` pass 1, for every cell: live = number of neighbours whose BIT 0 is 1 new = 1 if (live == 3) or (old == 1 and live == 2) else 0 g[i][j] = g[i][j] OR (new << 1)
pass 2, for every cell: g[i][j] = g[i][j] >> 1 ```
During pass 1 every cell still reports its old state through bit 0, whether or not it has been visited, so the neighbour count is always taken from the original grid. The shift in pass 2 promotes the new state and discards the old.
## Why the sentinel does not collide here
The trap in problem 1525 is that the marker and the data share an alphabet.
Here they do not: the data uses bit 0 and the marker uses bit 1, and the two
never interfere because reading g AND 1 ignores the marker entirely. Widening
the alphabet is the general escape from a sentinel collision, and it is
available exactly when the values do not already use the whole range.
## The neighbour loop and the edges
The eight offsets are every (di, dj) with di and dj in -1, 0, 1 except
(0,0). Each candidate must be range checked in BOTH coordinates before it is
read; on a 1 by C grid six of the eight are always outside, and on a 1 by 1
grid all eight are. The test with live cells in all four corners is there
because a missing check reads outside the grid exactly there.
## A live cell alone
A single 1 on a 1 by 1 grid has no neighbours at all, so it has fewer than two and dies. That is the smallest complete run of the rules.
## Overflow
Values are 0 and 1, and the encoding uses values 0 to 3, all far inside a
signed 32 bit integer whose limit is 2147483647.
## Cost
O(R C) time, eight neighbour reads per cell, and O(1) extra memory.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - every value is `0` or `1` - neighbours include the four diagonal ones, so a cell has at most eight - no second grid; `O(1)` extra memory beyond the input - `R` and `C` are independent; the grid need not be square
Input
The first line contains two integers R and C.
Each of the next R lines contains C integers, each 0 or 1.
Output
Print the grid after exactly one step, as R lines of C values each, separated by single spaces. Every printed value is 0 or 1 and the shape is unchanged.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.