20200402

生命游戏

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

• 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
• 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
• 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
• 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
• 根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。

示例：

输入：
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
输出：
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]

用二进制表示，用最后一位表示当前状态，倒数第二位表示下一状态

int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
void gameOfLife(vector<vector<int>>& board) {
    if(board.size() == 0) return;
    int n = board.size();
    int m = board[0].size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int cnt = 0;
            for(int k = 0; k < 8; k++){
                int x = i + dx[k];
                int y = j + dy[k];
                if(x < 0 || x>=n || y<0 || y>=m) continue;
                cnt += board[x][y] & 1;
            }
            if((board[i][j] & 1) > 0){// 这个是活细胞
                if(cnt >= 2 && cnt <= 3) board[i][j] = 0b11;// 周围有2/3个活细胞，下一个状态还是活细胞
                // 周围活细胞过多或过少都会死，因为原数据是0b01，所以这里不用额外赋值
            }
            else if(cnt == 3) board[i][j] = 0b10;
        }
    }
    // 最后一位去掉，倒数第二位变为更新后的状态。
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            board[i][j] >>= 1;
        }
    }
}