leetcodeノート:Game of Life

一.タイトルの説明
According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
Write a function to compute the next state (after one update) of the board given its current state.
二.テーマ分析
テーマは長いですが、大意は以下の通りです.0，1からなる行列が与えられ、各元素は1つの細胞の生存を表し、1は生存し、0は死亡し、そのうち次の更新は各細胞の生存は上、下、左、右、左上、左下、右上、右下、8つの細胞によって決定され、生存規則は以下の通りである.
現在の細胞が生存状態である場合、周囲の生存細胞が2個未満であると、その細胞は死亡状態となる.(アナログ生命の数は少ない)
現在の細胞が生存状態である場合、周囲に2つまたは3つの生存細胞がある場合、その細胞はそのままである.
現在の細胞が生存状態である場合、周囲に3個以上の生存細胞がある場合、その細胞は死亡状態となる.(シミュレーションライフの数が多すぎる)
現在の細胞が死亡状態である場合、周囲にちょうど3つの生存細胞がある場合、この細胞は生存状態となる.(繁殖シミュレーション)
行列の現在の状態に基づいて、この細胞行列の次の状態を計算する関数を書く必要があります.
テーマはin-place操作を要求し,各元素が付近の8元素の影響を受けることを考慮して,元素変化の前後の状態を反応させる中間状態を記録しなければならない.
幸いなことに、テーマは4つの変化状態を提供し、比較的直観的に構想を提供した.
状態0:死細胞->死細胞状態1:生細胞->生細胞状態2:生細胞->死細胞状態3:死細胞->生細胞
各要素について判断し、近くの8つの要素およびその状態から状態0~4のうちの1つを得ることができ、次の要素は依然として前の要素の状態0~4に基づいて、前の要素が変化する前にどのような状態であるかを判断することができる.
一方、すべての元素に対して状態0~4をマークした後、再び行列を巡り、すべての元素の状態が2に対して余りを取ると、状態0と2は死細胞となり、状態1と3は生細胞となり、目的を達成する.
三.サンプルコード

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int row = board.size();
        if (row == 0) return;
        int col = board[0].size();
        if (col == 0) return;

        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                int sum = checkNeighbor(board, i, j, row, col);
                if (sum == 2) continue;
                else if(sum == 3) board[i][j] = board[i][j] == 0 ? 3 : 1;
                else board[i][j] = board[i][j] == 0 ? 0 : 2;
            }
        }

        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < col; ++j)
            {
                board[i][j] %= 2;
            }
        }
    }

private:
    int checkNeighbor(vector<vector<int>>& board, int x, int y, int row, int col)
    {
        int count = 0;
        for (int i = x - 1; i <= x + 1; ++i)
        {
            for (int j = y - 1; j <= y + 1; ++j)
            {
                if (i == x && j == y) continue;
                else if (i >= 0 && i < row && j >= 0 && j < col && (board[i][j] == 1 || board[i][j] == 2))
                    ++count;
            }
        }
        return count;
    }
};

四.小結
このテーマはin-placeの要求の下で、面白いテーマです.