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