文档章节

LeetCode:Game of Life - 康威生命游戏

北风其凉
 北风其凉
发布于 2015/10/08 20:36
字数 1082
阅读 3011
收藏 0

1、题目名称

Game of Life(康威生命游戏)

2、题目地址

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

3、题目内容

英文:

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.

中文:

根据维基百科条目 Conway's Game of Life(康威生命游戏),康威生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。

给出一个m*n的细胞矩阵,每个细胞都有一个初始状态:生存(1)或死亡(0)。每个细胞的变化都与它周围8个细胞有关,规则如下:

  1. 当前细胞为存活状态时,当周围存活细胞不到2个时, 该细胞变成死亡状态。(模拟生命数量稀少)

  2. 当前细胞为存活状态时,当周围有2个或3个存活的细胞时, 该细胞保持原样。

  3. 当前细胞为存活状态时,当周围有3个以上的存活细胞时,该细胞变成死亡状态。(模拟生命数量过多)

  4. 当前细胞为死亡状态时,当周围恰好有3个存活细胞时,该细胞变成存活状态。 (模拟繁殖)

写一个函数,根据矩阵当前的状态,计算这个细胞矩阵的下一个状态。

4、解题方法

在不使用定义新矩阵的情况下,要想解决本问题就需要先定义一组中间状态,中间状态要求能看出一个单元格变化前后两方面的生死情况。Java代码如下:

/**
 * @功能说明:LeetCode 289 - Game of Life
 * @开发人员:Tsybius2014
 * @开发时间:2015年10月8日
 */
public class Solution {

    //死亡单位
    final int DEAD = 0;
    //存活单位
    final int ALIVE = 1;

    //变化情况:死亡→死亡
    final int DEAD_TO_DEAD = 0;
    //变化情况:存活→存活
    final int ALIVE_TO_ALIVE = 1;
    //变化情况:存活→死亡
    final int ALIVE_TO_DEAD = 2;
    //变化情况:死亡→存活
    final int DEAD_TO_ALIVE = 3;
    
    /**
     * 判断某点在本轮变化前是否是死亡状态
     * @param obj
     * @return
     */
    private boolean isAliveOld(int obj) {
        if (obj == ALIVE_TO_ALIVE || obj == ALIVE_TO_DEAD) {
            return true;
        }
        else {
            return false;
        }
    }

    /**
     * 判断某点在本轮变化后是否是死亡状态
     * @param obj
     * @return
     */
    private boolean isAliveNew(int obj) {
        if (obj % 2 == 1) {
            return true;
        } else {
            return false;
        }
    }
    
    /**
     * 生命游戏
     * @param board
     */
    public void gameOfLife(int[][] board) {

        //输入合法性检查
        if (board == null) {
            return;
        }
        int height = board.length;
        if (height == 0) {
            return;
        }
        int width = board[0].length;
        if (width == 0) {
            return;
        }

        //考察所有的点,变化其生命状态
        int counter = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                
                //统计周边生命生存情况
                counter = 0;
                if (i > 0 && j > 0 && isAliveOld(board[i - 1][j - 1])) {
                    counter++;
                }
                if (i > 0 && isAliveOld(board[i - 1][j])) {
                    counter++;
                }
                if (i > 0 && j < width - 1 && isAliveOld(board[i - 1][j + 1])) {
                    counter++;
                }
                if (j > 0 && isAliveOld(board[i][j - 1])) {
                    counter++;
                }
                if (j < width - 1 && isAliveOld(board[i][j + 1])) {
                    counter++;
                }
                if (i < height - 1 && j > 0 && isAliveOld(board[i + 1][j - 1])) {
                    counter++;
                }
                if (i < height - 1 && isAliveOld(board[i + 1][j])) {
                    counter++;
                }
                if (i < height - 1 && j < width - 1 && isAliveOld(board[i + 1][j + 1])) {
                    counter++;
                }
                
                //根据指定点周边的生命生存情况决定当前点的变化
                if (isAliveOld(board[i][j])) {
                    if (counter < 2) {
                        //1.存活单位周边的存活单位少于2个,该单位死亡
                        board[i][j] = ALIVE_TO_DEAD;
                    } else if (counter == 2 || counter == 3) {
                        //2.存活单位周边的存活单位有2-3个,该单位继续存活
                        board[i][j] = ALIVE_TO_ALIVE;
                    } else {
                        //3.存活单位周边的存活单位多余3个,该单位死亡
                        board[i][j] = ALIVE_TO_DEAD;
                    }
                } else {
                    if (counter == 3) {
                        //4.死亡单位周边的存活单位恰好为3个,该单位变为存活状态
                        board[i][j] = DEAD_TO_ALIVE;                    
                    } else {
                        board[i][j] = DEAD_TO_DEAD;
                    }
                }
            }
        }

        //根据变换后的存活状态,重新赋予每个点的生死情况
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (isAliveNew(board[i][j])) {
                    board[i][j] = ALIVE;
                } else {
                    board[i][j] = DEAD;
                }
            }
        }
    }
}

END

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 118
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
C语言做“生命游戏”

Algorithm Gossip: 生命游戏 生命游戏(game of life)为1970年由英国数学家J. H. Conway所提出,某一细胞的邻居包括上、下、左、右、左上、左下、右上与右下相邻的细胞,游戏规则如下: 孤单...

小辰GG
2017/11/30
0
0
4Clojure hard题目-94

4Clojure是一个面向clojure初学者的在线答题网站,问题从易到难,一步步辅助初学者深入了解clojure Game of Life Difficulty: Hard Topics: game The game of life is a cellular automaton...

池塘仙人
2012/11/13
333
0
细胞生死问题 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 197......

叶枫啦啦
2017/12/19
0
0
h5小游戏——HitRocket

一.游戏介绍 游戏介绍: 不断有携带字母炸弹的火箭撞向地面,请根据火箭身上的字母敲击键盘,每一次对应的敲击会击落携带该字母的火箭并使得分加一,每一架火箭撞到地面会使生命值减一,每击...

lonelydawn
2016/05/31
935
3
生活不是五月天的游戏

最近,我读到了一段19世纪的英国散文,很有感触。 这段话来自汤玛斯·卡莱尔(Thomas Carlyle,1795一1881)的《过去与现在》(Past and Present,1843)。 生命对于人们从来不是五月天的游戏;...

阮一峰
2005/12/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

创建多个git账号

实习开发中我们可能一个机子上配置多个git账号,如github.com,oschina.com 或者工作账号,私人账号,这时候就2个账号用一个key,肯定会冲突,有一个会提示没权限(账号和密码对应不上) ssh ...

echojson
28分钟前
1
0
rabbitmq安装教程

RabbitMQ有Windows与Linux版本的,这里先写Windows版本的安装。 以前安装软件总是在百度上找某某安装教程,结果能按照教程安装好的软件真的不多。想起先前以为大牛说的一句话,去官网按照官网...

em_aaron
今天
7
0
Android 贝塞尔曲线实践——波浪式运动

一、波浪效果如下 贝塞尔曲线自定义波浪效果的案例很多,同样方法也很简单,大多数和本案例一样使用二次贝塞尔曲线实现,同样还有一种是PathMeasure的方式,这里我们后续补充,先来看贝塞尔曲...

IamOkay
今天
3
0
Nmap之防火墙/IDS逃逸

选项 解释 -f 报文分段 --mtu 指定偏移大小 -D IP欺骗 -sI 原地址欺骗 --source-port 源端口欺骗 --data-length 指定发包长度 --randomize-hosts 目标主机随机排序 --spoof-mac Mac地址欺骗 ...

Frost729
今天
2
0
带你搭一个SpringBoot+SpringData JPA的环境

不知道大家对SpringBoot和Spring Data JPA了解多少,如果你已经学过Spring和Hibernate的话,那么SpringBoot和SpringData JPA可以分分钟上手的。 其实我在学完SpringBoot和SpringData JPA了之...

java菜分享
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部