leetcode 289. Game of Life 生命游戏

灰太狼 2022-06-08 14:24 147阅读 0赞

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.  
Any live cell with two or three live neighbors lives on to the next generation.  
Any live cell with more than three live neighbors dies, as if by over-population..  
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.  
Write a function to compute the next state (after one update) of the board given its current state.

Follow up:  
Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.  
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

**元胞自动机（Cellular Automaton/Automata）**中最著名的一组规则（该规则的想法可以追溯到冯·诺依曼，别名“生命游戏”）。每个细胞死或活的状态由它周围的八个细胞所决定。

1.  “人口过少”：任何活细胞如果活邻居少于2个，则死掉。
2.  “正常”：任何活细胞如果活邻居为2个或3个，则继续活。
3.  “人口过多”：任何活细胞如果活邻居大于3个，则死掉。
4.  “繁殖”：任何死细胞如果活邻居正好是3个，则活过来。

题目需要“就地解决”，我们不妨分析一下borad的特性：board上的元素有两种状态，生（1）和死（0）。这两种状态存在了一个int型里面。所以我们可以有效利用除最低位的其它位，去保存更新后的状态，这样就不需要有额外的空间了。

具体而言，我们可以用最低位表示当前状态，次低位表示更新后状态：

00(0)：表示当前是死，更新后是死；  
01(1)：表示当前是生，更新后是死；  
10(2)：表示当前是死，更新后是生；  
11(3)：表示当前是神，更新后是生。

代码如下：

/*
     * http://www.cnblogs.com/jdneo/p/5236373.html
     * 00(0)：表示当前是死，更新后是死；
     * 01(1)：表示当前是生，更新后是死；
     * 10(2)：表示当前是死，更新后是生；
     * 11(3)：表示当前是神，更新后是生。
     * */
    class Solution
    {
        public void gameOfLife(int[][] board) 
        {
            if (board == null || board.length == 0) 
                return;
            int m = board.length, n = board[0].length;
            for (int i = 0; i < m; i++) 
            {
                for (int j = 0; j < n; j++) 
                {
                    int lives = liveNeighbors(board, m, n, i, j);
                    // In the beginning, every 2nd bit is 0;
                    // So we only need to care about when will the 2nd bit become 1.
                    if (board[i][j] == 1 && lives >= 2 && lives <= 3) 
                        board[i][j] = 3; // Make the 2nd bit 1: 01 ---> 11
                    if (board[i][j] == 0 && lives == 3) 
                        board[i][j] = 2; // Make the 2nd bit 1: 00 ---> 10
                }
            }
    
            for (int i = 0; i < m; i++) 
            {
                for (int j = 0; j < n; j++)
                {
                    if(board[i][j]>=2)
                        board[i][j]=1;
                    else 
                        board[i][j]=0;
                }           
            }
        }
    
        public int liveNeighbors(int[][] board, int m, int n, int i, int j) 
        {
            int lives = 0;
            for (int x = Math.max(i - 1, 0); x <= Math.min(i + 1, m - 1); x++) 
            {
                for (int y = Math.max(j - 1, 0); y <= Math.min(j + 1, n - 1); y++) 
                {
                    lives += board[x][y] & 1;
                }           
            }
            lives -= board[i][j] & 1;
            return lives;
        }   
    }