Игра в Жизнь

Сегодня у нас будет интересная задача. Она даже больше нацелена на смекалку, чем на алгоритмы.

Сложность: 🟠 Cредняя

ℹ️ Описание

Доска состоит из сетки ячеек размером m x n, где каждая ячейка имеет начальное состояние:

🔹живое — обозначается цифрой 1
🔹мертвое — обозначается цифрой 0.

Каждая ячейка взаимодействует со своими восемью соседями (горизонтальными, вертикальными, диагональными), используя следующие четыре правила.

🔹Любая живая клетка, имеющая менее двух живых соседей, умирает, из-за недостаточной численности населения.

🔹Любая живая клетка с двумя или тремя живыми соседями доживает до следующего поколения.

🔹Любая живая клетка, имеющая более трех живых соседей, погибает от перенаселения.

🔹Любая мертвая клетка, имеющая ровно три живых соседа, становится живой клеткой путем размножения.

Следующее состояние доски создается путем одновременного применения вышеуказанных правил к каждой ячейке в текущем состоянии, где рождение и смерть происходят одновременно.

Напишите функцию, которая принимает на вход матрицу состояния и изменяет ее до следующего состояния.

Механика игры подробно описана в статье википедии.

⚠️ Ограничения

🔹В матрице может быть от 1 до 25 столбцов и колонок
🔹В каждой ячейке может быть всего одно значение: 0 или 1

1️⃣ Пример

Входящие данные:
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0],
]

Ответ:
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0],
]

2️⃣ Пример

Входящие данные:
[
[1,1],
[1,0]
]

Ответ:
[
[1,1],
[1,1],
]

✅ Решение

Эту задачу очень просто решить, если реализовать изменение матрицы в ее копии. Это делает алгоритм очень простым, но требует выделения дополнительной памяти, что может стать проблемой при большом количестве данных.

Чтобы иметь оптимальное потребление памяти, нужно производить все изменения in-place. Если мы будем просто менять состояние в исходной матрице при проверке каждого элемента, то мы потеряем исходное состояние и не сможем корректно проверять необходимость мутации.

Для того чтобы это обойти введем два новых значения для матрицы.

🔘2 обозначает переход нуля в единицу. Мы будем использовать двойку в качестве значения, чтобы пометить неживые клетки, которые должны стать живыми по итогам наших расчетов.

🔘3 обозначает переход единицы в ноль. Мы будем использовать тройку в качестве значения, чтобы пометить живые клетки, которые должны стать неживыми по итогам наших расчетов.

При вычислении состояния для каждой клетки нужно учитывать эти нововведения. В конце после того, как мы поменяем состояния для всех элементов матрицы нужно еще раз обновить ее и заменить все 2 на 0, а 3 на 1.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени
O(m * n) так как мы обходим всю матрицу поэлементно.

По памяти
O(1) так как мы не выделяем дополнительную память.

#matrix #medium