1. Идея

Нужно смоделировать игру «Жизнь» на прямоугольном поле в течение k шагов.

На каждом шаге состояние каждой клетки зависит только от:

• её текущего состояния;
• количества живых соседей среди 8 возможных.

Самое естественное решение — просто выполнять симуляцию шаг за шагом:

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

Важно, что все клетки обновляются одновременно. Значит, нельзя менять поле "на месте", иначе уже обновлённые клетки начнут влиять на ещё не обработанные. Поэтому нужен отдельный массив next_grid.

2. Наблюдения

Наблюдение 1. У клетки всегда не более 8 соседей

Соседи — это клетки по горизонтали, вертикали и диагонали. Удобно заранее сохранить их смещения:

• (-1, -1)
• (-1, 0)
• (-1, 1)
• (0, -1)
• (0, 1)
• (1, -1)
• (1, 0)
• (1, 1)

Тогда для клетки (r, c) можно перебрать все 8 направлений и проверить, лежит ли сосед внутри поля.

Наблюдение 2. Клетки вне поля считаются мёртвыми

Это означает, что при подсчёте соседей достаточно учитывать только те координаты, которые находятся в пределах:

• 0 <= nr < n
• 0 <= nc < m

Если координаты выходят за границы, такую клетку просто игнорируем.

Наблюдение 3. Правила перехода очень локальные

Для каждой клетки достаточно знать только число живых соседей alive.

Дальше правила такие:

• если клетка живая ('X'), то она остаётся живой только при alive == 2 или alive == 3;
• если клетка мёртвая ('.'), то она оживает только при alive == 3.

Наблюдение 4. Ограничения позволяют прямую симуляцию

Максимальные значения:

• n <= 200
• m <= 200
• k <= 200

На одном шаге:

• n * m клеток;
• для каждой смотрим до 8 соседей.

То есть всего порядка k * n * m * 8, что укладывается без проблем.

3. Алгоритм

Пусть текущее поле хранится в grid.

Для каждого из k шагов:

1. Создаём новое поле next_grid, целиком заполненное символами '.'.
2. Для каждой клетки (r, c):
   • считаем количество живых соседей alive;
   • перебираем все 8 направлений;
   • если сосед внутри поля и в grid там 'X', увеличиваем alive.
3. Применяем правила:
   • если grid[r][c] == 'X':
     • при alive == 2 или alive == 3 в next_grid[r][c] записываем 'X';
     • иначе оставляем '.';
   • если grid[r][c] == '.':
     • при alive == 3 записываем 'X';
     • иначе оставляем '.'.
4. После обработки всех клеток присваиваем grid = next_grid.

После завершения всех шагов выводим поле.

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

Докажем, что алгоритм действительно получает правильное состояние поля после k шагов.

Рассмотрим один произвольный шаг симуляции.

Для каждой клетки алгоритм:

1. точно перебирает все 8 возможных соседних позиций;
2. учитывает только те из них, которые находятся внутри поля;
3. среди них подсчитывает ровно те клетки, которые живы в текущем состоянии grid.

Значит, число alive совпадает с количеством живых соседей по условию задачи.

Далее алгоритм применяет к клетке точно те же правила, что заданы в условии:

• живая клетка выживает при 2 или 3 соседях;
• мёртвая оживает при 3 соседях;
• во всех остальных случаях клетка мертва.

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

Таким образом, после одного шага next_grid совпадает с правильным состоянием поля после одного применения правил.

Повторяя этот процесс k раз, получаем правильное состояние после ровно k шагов.

5. Сложность

На каждом из k шагов:

• обрабатывается n * m клеток;
• для каждой проверяются 8 соседей.

Итоговая сложность:

• O(k * n * m * 8), что обычно записывают как O(k * n * m).

По памяти:

• храним текущее и следующее поле размера n * m.

Итоговая память:

• O(n * m).

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

    for (int step = 0; step < k; step++) {
        vector<string> next_grid(n, string(m, '.'));

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                int alive = 0;

                for (int d = 0; d < 8; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 'X') {
                        alive++;
                    }
                }

                if (grid[r][c] == 'X') {
                    if (alive == 2 || alive == 3) {
                        next_grid[r][c] = 'X';
                    } else {
                        next_grid[r][c] = '.';
                    }
                } else {
                    if (alive == 3) {
                        next_grid[r][c] = 'X';
                    } else {
                        next_grid[r][c] = '.';
                    }
                }
            }
        }

        grid = next_grid;
    }

    for (int i = 0; i < n; i++) {
        cout << grid[i] << '\n';
    }

    return 0;
}

7. Код на Python 3

n, m, k = map(int, input().split())
grid = [list(input()) for _ in range(n)]

dr = [-1, -1, -1, 0, 0, 1, 1, 1]
dc = [-1, 0, 1, -1, 1, -1, 0, 1]

for _ in range(k):
    next_grid = [['.' for _ in range(m)] for _ in range(n)]

    for r in range(n):
        for c in range(m):
            alive = 0
            for d in range(8):
                nr = r + dr[d]
                nc = c + dc[d]
                if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 'X':
                    alive += 1

            if grid[r][c] == 'X':
                if alive == 2 or alive == 3:
                    next_grid[r][c] = 'X'
            else:
                if alive == 3:
                    next_grid[r][c] = 'X'

    grid = next_grid

for row in grid:
    print(''.join(row))