Game Life

发表于 | 分类于

Game Life(生存游戏)

题目描述：

给定一个矩阵，矩阵中只包含着0，1数字。有如下游戏规则：

  • 如果矩阵中的一个点当前值为1，且其周围为1的个数大于3或者小于2的时候，下一轮这个点为0；
  • 如果矩阵中的一个点当前值为0，当且仅当周围为1的个数为3的时候，这个点下一轮为1；

要求在O(1)的空间下找到下一轮的每个点的生存情况。

例子：

详细说明见leetcode

解题思路：

本题主要是在于空间上我们不能利用保存一个和当前矩阵相同的矩阵用来判断下一轮的节点情况；所以这边主要利用的是哈希表，我们建立一个哈希表；分别表示由1变1，由0变0，由1变0，由0变1的4种情况。在遍历矩阵的过程中，找到周围的8个点，从哈希表中找到对应的上一轮的节点情况用来判断当前节点的下一轮的情况。

代码如下：

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
class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        map<int, int> hash = {{-1, 0}, {-2, 1}, {1, 1}, {0, 0}};
        //表示4种变化情况
        int count = 0;
        int row = board.size();
        int col = board[0].size();
        //找到行和列
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                count = 0;
                count += (i - 1 >= 0 && j - 1 >= 0) ? hash[board[i - 1][j - 1]] : 0;
                count += (i - 1 >= 0) ? hash[board[i - 1][j]] : 0;
                count += (i - 1 >= 0 && j + 1 < col) ? hash[board[i - 1][j + 1]] : 0;
                count += (j - 1 >= 0) ? hash[board[i][j - 1]] : 0;
                count += (j + 1 < col) ? hash[board[i][j + 1]] : 0;
                count += (i + 1 < row && j - 1 >= 0) ? hash[board[i + 1][j - 1]] : 0;
                count += (i + 1 < row) ? hash[board[i + 1][j]] : 0;
                count += (i + 1 < row && j + 1 < col) ? hash[board[i + 1][j + 1]]: 0; 
                //计算周围8个节点的情况
                if (board[i][j] == 1 && (count > 3 || count < 2))
                    board[i][j] = -2;
                    //针对两种情况进行变化
                else if (board[i][j] == 0 && count == 3)
                    board[i][j] = -1;
            }
        }
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                if (board[i][j] == -1)
                    board[i][j] = 1;
                if (board[i][j] == -2)
                    board[i][j] = 0;
                    //根据哈希表重建当前表
            }
        }
    }
};