跳转至

289.Game of Life

Tags: Medium Array

Links: https://leetcode.com/problems/game-of-life/

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):

  1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population..
  4. 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. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

Input: 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
Output: 
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

Follow up:

  1. 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.
  2. 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?

假如没有follow up的部分，则可以直接利用类似Lake Counting的问题来求解，搜索每个细胞周围八个位置的细胞状态，题目里同时更新的意思是，给定的borad数组就是一个历史映像，更新后的状态存储在新的矩阵里，最后再更新board。

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = board.size(); if (!m) return; 
        int n = board[0].size(); if (!n) return;
        vector<vector<int>> res(m, vector<int>(n));

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j]) {
                    int cnt = 0; //统计周围活细胞数量
                    for (int row = -1; row <= 1; ++row) {
                        int nextRow = i + row;
                        for (int col = -1; col <= 1; ++col) {
                            if (row == 0 && col == 0) continue;
                            int nextCol = j + col;
                            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && board[nextRow][nextCol]) ++cnt;
                        }
                    }

                    if (cnt == 2 || cnt == 3) res[i][j] = 1;
                    else res[i][j] = 0;
                }
                else {
                    int cnt = 0; //统计死细胞周围活细胞数量
                    for (int row = -1; row <= 1; ++row) {
                        int nextRow = i + row;
                        for (int col = -1; col <= 1; ++col) {
                            if (row == 0 && col == 0) continue;
                            int nextCol = j + col;
                            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && board[nextRow][nextCol]) ++cnt;
                        }
                    }
                    if (cnt == 3) res[i][j] = 1;
                    else res[i][j] = 0;
                }
            }
        }

        board = res;
    }
};

继续看follow up的部分，如果不允许另外开辟空间怎么办？如果有一个细胞的状态从0变为1，那么当访问其周围的细胞的时候，怎么知道上一个细胞之前的状态？那么联想之前一道题Set Matrix Zero，既然不允许额外开辟空间，那么就需要在原空间进行标记，所以问题的关键在于如何做标记。

0 从死细胞变为死细胞
1 从活细胞变为活细胞
2 活细胞变为死细胞
3 死细胞变为活细胞

最后只需要各个位置对2取模即可。注意的是，死细胞和活细胞的状态要对应好。

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int m = board.size(); if (!m) return; 
        int n = board[0].size(); if (!n) return;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j]) {
                    int cnt = 0; //统计周围活细胞数量(统计1和3)
                    for (int row = -1; row <= 1; ++row) {
                        int nextRow = i + row;
                        for (int col = -1; col <= 1; ++col) {
                            if (row == 0 && col == 0) continue;
                            int nextCol = j + col;
                            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && (board[nextRow][nextCol] == 1 || board[nextRow][nextCol] == 2)) ++cnt;
                        }
                    }

                    if (cnt == 2 || cnt == 3) board[i][j] = 1;
                    else board[i][j] = 2;
                }
                else {
                    int cnt = 0; //统计死细胞周围活细胞数量
                    for (int row = -1; row <= 1; ++row) {
                        int nextRow = i + row;
                        for (int col = -1; col <= 1; ++col) {
                            if (row == 0 && col == 0) continue;
                            int nextCol = j + col;
                            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && (board[nextRow][nextCol] == 1 || board[nextRow][nextCol] == 2)) ++cnt;
                        }
                    }
                    if (cnt == 3) board[i][j] = 3;
                    else board[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                board[i][j] %= 2;
            }
        }
    }
};