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的格子输俩个

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;
                }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49