Game of Life (M)

題目

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?

題意

細胞游戲：一個細胞有生死兩種狀態，如果一個細胞周圍活著的細胞個數小于2或大于3，則該細胞死亡；若個數為2，則狀態不變；若個數為3，則該細胞生還，給定某一個時刻的細胞狀態陣列，要求回傳下一時刻的細胞狀態陣列，

思路

題目要求狀態的變化是同時進行的，因此不能先計算出一個細胞的狀態，再用這個更新后的狀態去計算其他細胞的狀態，且要求僅在原陣列上進行修改，

最簡單的方法是直接將原陣列復制一份，每次查詢鄰接生存細胞個數都以這個拷貝陣列為基準，

原地修改方法：擴展陣列中的值型別如下:
0 -- dead -> dead
1 -- live -> live
2 -- dead -> live
3 -- live -> dead
第一次遍歷，將陣列中的值按要求修改為擴展值，第二次遍歷再將修改完的擴展值改回0和1，

代碼實作

Java

拷貝

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        int[][] copy = new int[m][];
        for (int i = 0; i < m; i++) {
            copy[i] = Arrays.copyOf(board[i], n);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = count(copy, i, j, m, n);
                if (count < 2 || count > 3) {
                    board[i][j] = 0;
                } else if (count == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }

    private int count(int[][] board, int i, int j, int m, int n) {
        int[] diff = { -1, 0, 1 };
        int count = 0;
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                int nextI = i + diff[x], nextJ = j + diff[y];
                if (!(x == 1 && y == 1) && isValid(nextI, nextJ, m, n) && board[nextI][nextJ] == 1) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
}

原地

class Solution {
    public void gameOfLife(int[][] board) {
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int count = count(board, i, j, m, n);
                int origin = board[i][j];
                if (count < 2 || count > 3) {
                    board[i][j] = origin == 0 ? 0 : 3;
                } else if (count == 3) {
                    board[i][j] = origin == 0 ? 2 : 1;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int value = https://www.cnblogs.com/mapoos/p/board[i][j];
                board[i][j] = value == 3 ? 0 : value == 2 ? 1 : value;
            }
        }
    }

    private int count(int[][] board, int i, int j, int m, int n) {
        int[] diff = { -1, 0, 1 };
        int count = 0;
        for (int x = 0; x < 3; x++) {
            for (int y = 0; y < 3; y++) {
                int nextI = i + diff[x], nextJ = j + diff[y];
                if (!(x == 1 && y == 1) && isValid(nextI, nextJ, m, n) && board[nextI][nextJ] % 2 == 1) {
                    count++;
                }
            }
        }
        return count;
    }

    private boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        s.gameOfLife(new int[][] { { 0, 1, 0 }, { 0, 0, 1 }, { 1, 1, 1 }, { 0, 0, 0 } });
    }
}

標籤：其他

上一篇：0037. Sudoku Solver (H)

下一篇：是不是家用路由器不支持在無線下進行組播multicast