game of life

算法 array

题意：给定生命游戏（元胞自动机）的现有状态，根据规则计算下一个状态。

进阶:

你可以使用原地算法解决本题吗？请注意，面板上所有格子需要同时被更新：你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
本题中，我们使用二维数组来表示面板。原则上，面板是无限的，但当活细胞侵占了面板边界时会造成问题。你将如何解决这些问题？

分析：

题目中要求in-place解题，那么只能更新原有数组上进行更新。参考别人实现的一个方法，结果别人给出的就地解法竟然只是把前后两个状态通过位运算的方法硬塞进一个int里。它利用的是编程语言的性质，而非真正的数学思路。从抽象的角度来说，每个格子只有位置信息和1 bit的状态信息。

后来看了另一份题解,其思路其实相当于我们在这个元胞自动机的每一个格子里又塞了一个有限状态自动机。

后来读了chapter-17-the-game-of-life和chapter-18-its-a-plain-wonderful-life得到了更大的启发。这本书中给出了对模拟生命游戏进行进一步的速度优化的两种主要思路：

关注数据的实际状态。通过生命游戏的规则，我们很容易看出，活细胞的数量不会太多，而且细胞状态的变化并不频繁。因此，我们可以维护一张实际变化了的细胞位置的表，并在更新时主要处理这张表指向的细胞。

状态压缩。除了像上面说的那样，把当前和未来状态打包起来以外，我们还可以把相邻活细胞的数量也记为状态的一部分，甚至还可以把多个细胞的状态一起压缩。除了减少空间占用之外，查表的复杂度也减小了

书中David Stafford的解法把这几种思路有机地结合在了一起，创造了一份非常精妙的代码，以至于我很难分别描述每种思路各自的好处

对于棋盘无穷大的情形：

即使细胞有无穷多个，活细胞的数目也应该是有限的，所以我们只需分别更新每个活细胞及其周围细胞的状态即可。

代码：

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int n = board.size();
        if (n < 1)
            return;
        int m = board[0].size();
        // 直接将原状态保存下来
        vector<vector<int>> original;
        for (int i = 0; i < n; i++) {
            vector<int> tmp;
            for (int j = 0; j < m; j++)
                tmp.push_back(board[i][j]);
            original.push_back(tmp);
        }

        // 更新board
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cnt = 0;
                if (i > 0) cnt += original[i-1][j];
                if (i < n-1) cnt += original[i+1][j];
                if (j > 0) cnt += original[i][j-1];
                if (j < m-1) cnt += original[i][j+1];
                if (i > 0 && j > 0) cnt += original[i-1][j-1];
                if (i > 0 && j < m-1) cnt += original[i-1][j+1];
                if (i < n-1 && j > 0) cnt += original[i+1][j-1];
                if (i < n-1 && j < m-1) cnt += original[i+1][j+1];

                if (original[i][j] == 1) {
                    if (cnt < 2 || cnt > 3)
                        board[i][j] = 0;
                    else
                        board[i][j] = 1;
                }
                else if (cnt == 3)
                    board[i][j] = 1;
            }
        }
    }
};

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com