289 Game of Life 生命的游戏

假设有一个大小为m*n的板子，有m行，n列个细胞。每个细胞有一个初始的状态，死亡或者存活。每个细胞和它的邻居（垂直，水平以及对角线）。互动规则如下：
1.当前细胞存活时，周围低于2个存活细胞时，该细胞死亡。（模拟生物数量过少，导致死亡）
2.当前细胞存活时，周围有2个~3个存活细胞时，该细胞保持原状态。
3.当前细胞存活时，周围有3个以上存活细胞时，该细胞死亡。（模拟生物数量过大导致死亡）
4.当前细胞死亡时，周围存在3个存活细胞时，该细胞变成存活状态。（生活繁殖）
写一个函数，根据当前的状态计算下一个状态。
进阶：
1，就地解决问题？记住，该空间需要同时更新。不能首先更新一部分，然后再用这些新的状态去更新其他的细胞。
2，在这个问题吗，我们使用了二维数组。原则上空间无限大。这些变化影响到边界时，如何处理？

详见：https://leetcode.com/problems/game-of-life/description/

class Solution {

public:

    void gameOfLife(vector<vector<int>>& board) {

        int rows = board.size();

        int cols = board[0].size();

        for(int i = 0; i < rows; ++i){

            for(int j = 0; j < cols; ++j){

                int neighbors = getNeighbors(board,i,j);

                //如果当前细胞是活的

                if((board[i][j] & 1) == 1){

                    //如果活细胞周围邻居有两道三个为活细胞，则下一代继续存活

                    if(neighbors == 2  || neighbors == 3){

                        board[i][j] = 3;

                    }

                    //如果是01，则在更新时，死掉

                    //如果小于2个或者大于3个，都是导致死亡

                }else{

                    //如果当前细胞是死的，其相邻有三个或者的邻居。则其变成一个活细胞

                    if(neighbors == 3){

                        board[i][j] = 2;

                    }

                }

            }

        }

        for(int i = 0; i < rows; ++i){

            for(int j = 0; j < cols;++j){

                board[i][j] = board[i][j] >> 1;

            }

        }

    }

    //统计为1的邻居个数

    int getNeighbors(vector<vector<int> > &board,int r,int c){

        int rows = board.size();

        int cols = board[0].size();

        int res = 0;

        for(int i = std::max(0,r-1); i <= std::min(rows-1,r+1);++i){

            for(int j = std::max(0,c-1); j <= std::min(cols-1,c+1); ++j){

                res += board[i][j]&1;

            }

        }

        res -= board[r][c]&1;

        return res;

    }

};

参考：https://blog.csdn.net/sjwl2012/article/details/54344670

https://www.cnblogs.com/grandyang/p/4854466.html

巴特西

289 Game of Life 生命的游戏

最新文章

热门文章