leetcode 289. 生命游戏-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 289. 生命游戏。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目链接：leetcode 289

1.题目

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

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

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

2.示例

1）示例 1：
输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

2）示例 2：
输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

3）提示：
m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 为 0 或 1

3.分析

首先我们看题目中给定的四条规则可以发现当前格子的状态变化只与周围八个格子中是活细胞的格子数量有关。同时初始时刻为活细胞且不改变可以表示为1，当它下一时刻为死细胞可以表示为2，而死细胞下一时刻为1可以表示为-1，那么规则转化为找周围8个格子中为1或2的格子输俩个文章来源地址https://www.toymoban.com/news/detail-705821.html

4.代码

class Solution {
public:
//1.basic
    int m,n;
    vector<vector<int>> ans;
    bool check(int x,int y){
        if(x<0||x>=m) return false;
        if(y<0||y>=n) return false;
        return true;
    }
    void gameOfLife(vector<vector<int>>& board) {
        //1.change_s
        m=board.size();
        if(m==0) return;
        n=board[0].size();
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(board[i][j]==0){
                    int cnt=0;
                    for(int ux=-1;ux<=1;ux++)
                        for(int uy=-1;uy<=1;uy++)
                                if(check(i+ux,j+uy))
                                    if(board[i+ux][j+uy]==1)
                                        cnt++;
                    if(cnt==3) board[i][j]=2;
                }
        //2.change_h
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(board[i][j]==1){
                    int cnt=0;
                    for(int ux=-1;ux<=1;ux++)
                        for(int uy=-1;uy<=1;uy++)
                            if(ux!=0||uy!=0)
                                if(check(i+ux,j+uy))
                                    if(board[i+ux][j+uy]==1||board[i+ux][j+uy]==-1)
                                        cnt++;
                    if(cnt!=2&&cnt!=3) board[i][j]=-1;
                }
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(board[i][j]==-1)
                    board[i][j]=0;
                else{
                    if(board[i][j]==2)
                      board[i][j]=1;
                }
    }
};