Почему не работает программа на C++ с решением задачи об «Игре в жизнь»?

Question

[Xiran]

Правила

• Место действия игры — размеченная на клетки неограниченная плоскость.
  
• Каждая клетка имеет 8 соседей (сверху, снизу, слева, справа и по диагоналям) и может находиться в двух состояниях: быть живой или мертвой.
  
• В пустой (мертвой) клетке, с которой соседствуют ровно 3 живые, зарождается жизнь.
  
• Если у живой клетки ровно 2 или ровно 3 живых соседа, то она продолжает жить, иначе погибает
  

Игровое поле

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

Мой код

#include <iostream>
#include <limits>
#include <vector>

constexpr std::size_t N = 208, M = 206;
using game_map_t = bool[N][M];

using set_cells_t = std::vector<std::pair<std::size_t, std::size_t>>; 

void set(const set_cells_t &input, game_map_t &map) {
    for (const auto &[i, j] : input)
        map[i][j] = true;
}

int count_live_neighbour_cell(game_map_t &map, int r, int c);

int main() {
    game_map_t map = {};

    set_cells_t set_cells {
        { 1, 2 },
        { 2, 3 },
        { 3, 1 },
        { 3, 2 },
        { 3, 3 },
        { 205, 204 },
        { 206, 204 },
        { 207, 204 }
    };

    int alive_count = set_cells.size();

    set(set_cells, map);

    for (int k = 0; k < std::numeric_limits<int>::max(); k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                const int alive_neighbours_count = count_live_neighbour_cell(map, i, j);

                if (!map[i][j] && alive_neighbours_count == 3) {
                    map[i][j] = true;
                    alive_count++;
                } else if (map[i][j] && alive_neighbours_count != 2 && alive_neighbours_count != 3) {
                    map[i][j] = false;
                    alive_count--;
                }

                if (alive_count == 0) {
                    std::cout << k + 1;
                    return 0;
                }
            }
        }
    }
}

int count_live_neighbour_cell(game_map_t &map, int r, int c) {
    int i, j, count = 0;
    for (i = r - 1; i <= r + 1; i++) {
        for (j = c - 1; j <= c + 1; j++) {
            if ((i == r && j == c) || (i < 0 || j < 0)
                || (i >= N || j >= M)) {
                continue;
            }
            if (map[i][j] == 1) {
                count++;
            }
        }
    }
    return count;
}

Не выдает решение и не останавливается. Что не так?

Comments

[Adamos]

Есть нюанс: в Жизни есть бессмертные расклады - как циклические на одном месте, так и "движущиеся", пока не закончится поле.
На ограниченном поле вторыми можно пренебречь, а вот ради учета первых имеет смысл через несколько секунд расчета сохранить текущее состояние и сравнивать каждое следующее с этим слепком, а при совпадении остановить-таки программу с соответствующим сообщением. Nevermore, так сказать.

Answer 1

[Wataru]

У вас ошибка в логике: вы меняете поле отдельно в каждой клетке. И потом используете уже поменянные клетки для подсчета количества соседей в следующей клетке. Но в игре жизнь все клетки считаются параллельно.

Для этого вам понадобится 2 массива map. Один для текущей итерации, и другой для следующей. Или массив должен быть не bool, а int, и там вы должны разными числами помечать живые клетки, которые умрут, живые клетки, пустые клетки и пустые клетки, которые родятся. В первый проход вы считаете соседей и помечаете клетки, а вторым проходом все изменения применяете.

Кажется, из-за этого у вас там поле никогда не вымирает и программа не останавливается.

Comments

[Xiran]

Спасибо, помогло, программа правильно решила. Буду знать. Отдельное спасибо за оперативность)