5246. Следующее поколение игры «Жизнь»

Дана прямоугольная таблица board из нулей и единиц — текущее поколение игры «Жизнь» Конвея. 1 означает живую клетку, 0 — мёртвую.

Посчитайте следующее поколение и верните таблицу того же размера (столько же строк и столбцов).

Соседи клетки — все восемь клеток вокруг, включая диагонали. Клеток за краем поля нет: у угловой клетки всего 3 соседа, у клетки на стороне — 5.

соседи клетки *:
. . .
. * .
. . .

Все клетки меняются одновременно: новое значение считается только по текущему поколению. Нельзя идти по таблице и сразу перезаписывать клетку — соседи ещё должны видеть старое состояние.

Пусть у клетки k живых соседей:

• живая и k < 2 → умирает (мало соседей);
• живая и k = 2 или k = 3 → остаётся живой;
• живая и k > 3 → умирает (слишком тесно);
• мёртвая и k = 3 → становится живой;
• иначе мёртвая остаётся мёртвой.

Менять исходную таблицу на месте не обязательно — достаточно вернуть новую.

Пример одного шага (это первый пример ниже):

сейчас          следующее
0 1 0           0 0 0
0 0 1     →     1 0 1
1 1 1           0 1 1
0 0 0           0 1 0

Верхняя живая клетка имеет только одного живого соседа — умирает. Нижняя средняя мёртвая клетка имеет ровно трёх живых соседей — рождается.