289. Life of Game

chuyao 发布于2019-08-14 16:31 / 2718人阅读

摘要：问题解答我的解法是需要最多的空间的。如果要做到那么我看到里一个非常的做法是用一个的数表示改变前和改变后的状态。

问题：
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?

解答：
我的解法是需要最多o(mn)的空间的。

class Point {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public void checkAlive(int[][] board, int val, int i, int j, List list) {
    int count = 0;
    int[][] dir = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    for (int k = 0; k < dir.length; k++) {
        int x = i + dir[k][0], y = j + dir[k][1];
        if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1) continue;
        count += board[x][y];
    }
    if (val == 1 && (count < 2 || count > 3)) {
        list.add(new Point(i, j));
    }
    if (val == 0 && count == 3) {
        list.add(new Point(i, j));
    }
}

public void gameOfLife(int[][] board) {
    if (board == null || board.length == 0 || board[0].length == 0) return;
    int m = board.length, n = board[0].length;
    List list = new ArrayList();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            checkAlive(board, board[i][j], i, j, list);
        }
    }
    for (int i = 0; i < list.size(); i++) {
        Point p = list.get(i);
        board[p.x][p.y] = board[p.x][p.y] == 1 ? 0 : 1;
    }
}

如果要做到in space, 那么我看到discussion里一个非常tricky的做法是用一个2-bit的数表示改变前和改变后的状态。改变前有两个状态：00, 01. 在满足一定的条件后，改变前一个bit的状态也有两种：10, 11.所以我们只要记录改变的状态，然后将实际的数向后移动一位就可以得到当然的一状态。

public int helper(int[][] board, int i, int j) {
    int count = 0;
    int[][] dir = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
    for (int k = 0; k < dir.length; k++) {
        int x = i + dir[k][0], y = j + dir[k][1];
        if (x < 0 || x > board.length - 1 || y < 0 || y > board[0].length - 1) continue;
        count += board[x][y] & 1;
    }
    return count;
}
public void gameOfLife(int[][] board) {
    if (board == null || board.length == 0 || board[0].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 = helper(board, i, j);
            if (board[i][j] == 1 && (lives == 2 || lives == 3)) {
                board[i][j] = 3;
            }
            if (board[i][j] == 0 && lives == 3) {
                board[i][j] = 2;
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] >>= 1;
        }
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66212.html

[LeetCode] 289. Game of Life

Problem According to the Wikipedias 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 ...

Ajian 2019-08-19 11:16 评论0 收藏0
leetcode289. Game of Life

摘要：板上的每个小格子有两种状态，或。而根据游戏规则，每一次这个板上的内容将会随着前一次板上的内容发生变化。然后再根据当前格子的状态计算当前格子的下一个状态。当然最后别忘了将原始状态传递出去。题目要求 According to the Wikipedias article: The Game of Life, also known simply as Life, is a cellular...

jerryloveemily 2019-08-15 14:30 评论0 收藏0
[Leetcode] Game of Life 生命游戏

摘要：思路普通解法，遍历每一个细胞求值，用一个的矩阵存放结果。求值过程，稍微分析一下可知，其实就是按照以下的矩阵进行结果是可数的。 According to the Wikipedias article: The Game of Life, also knownsimply as Life, is a cellular automaton devised by the Britishmath...

android_c 2019-08-15 13:59 评论0 收藏0
Python+Pygame实操之玩命吃水果游戏的完成

　　吃豆人和削苹果这两个游戏想必大家都知道吧，本文运用Python里的Pygame控制模块编写出一个融合吃豆人+切水果的新手游：玩命吃苹果，有兴趣的话可以认识一下　　引言　　哈哈哈！木木子今天浮现——早已来给大家看了不少具体内容啦~　　涉及到的人工智能、新手、网络爬虫、数据统计分析（这一块的通常但是审批）手机游戏...　　PS:　　吃豆人我写过了哈　　Python+Pygame实战之吃豆豆游戏的实...

89542767 2022-12-25 20:26 评论0 收藏0
[Leetcode] Game of Life 生命游戏

摘要：如果多核的机器如何优化因为是多核，我们可以用线程来实现并行计算。如果线程变多分块变多，边缘信息也会变多，开销会增大。所以选取线程的数量是这个开销和并行计算能力的折衷。 Game of Life I According to the Wikipedias article: The Game of Life, also known simply as Life, is a cellula...

XFLY 2019-08-14 12:41 评论0 收藏0