Game of Life

Средняя№289старое и новое в клетке

Дана доска клеток: 1 — живая, 0 — мёртвая. Нужно получить следующее поколение, все клетки сразу, на месте. Каждая клетка смотрит на своих соседей, их до восьми: живая клетка с 2 или 3 живыми соседями живёт дальше, с меньшим или большим числом умирает; мёртвая с ровно 3 оживает. Наш пример: [0, 0, 0], [1, 1, 1], [0, 0, 0] → [0, 1, 0], [0, 1, 0], [0, 1, 0].

289 Game of LifeРазбор · 1×

Пример: ряд из трёх посередине [0, 0, 0], [1, 1, 1], [0, 0, 0]. Смотрите на клетку (2, 1): её соседи (1, 0) и (1, 2) уже помечены к смерти, но всё равно считаются.

012012000111000
0: мёртвая1: живая2: живая, умрёт3: мёртвая, родится

Первый проход: решаем следующее состояние каждой клетки по соседям, какими они были в этом поколении, и не теряем, что в клетке сейчас

01/29
сначала · назад · пуск · шаг
Скорость
1function gameOfLife(m):
2 for each cell (r, c):
3 live = neighbours of (r, c) that are 1 or 2
4 if m[r][c] == 1 and (live < 2 or live > 3):
5 m[r][c] = 2 // alive now, dead next
6 else if m[r][c] == 0 and live == 3:
7 m[r][c] = 3 // dead now, alive next
8 for each cell (r, c):
9 m[r][c] = m[r][c] mod 2 // keep the new state
10 return m
состояние
r
–
c
–
live
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждую клетку нужно решать по доске, какой она была. Если сразу писать 0 или 1, поменяется счёт у следующих клеток: (2, 1) увидела бы одного живого соседа вместо трёх и осталась мёртвой.
  2. Пометки хранят оба состояния в одной клетке: 1 или 2 — живая сейчас, 0 или 3 — мёртвая сейчас, поэтому счёт верен, пока доска заполняется решениями; а 2 или 3 ещё и говорят, что клетка меняется.
  3. Когда все клетки решены, старые состояния больше не нужны. Новое состояние — это значение mod 2 (0 и 2 — мёртвая в следующем поколении, 1 и 3 — живая), поэтому второй проход — одна строка без проверок.

Сложность

Время O(строки × столбцы): каждая клетка один раз смотрит на не больше восьми соседей и один раз расшифровывается. Память O(1): копии доски нет, пометки живут в клетках.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.