leetcode289. Game of Life

jerryloveemily 發布于2019-08-15 14:30 / 2082人閱讀

摘要：板上的每個小格子有兩種狀態，或。而根據游戲規則，每一次這個板上的內容將會隨著前一次板上的內容發生變化。然后再根據當前格子的狀態計算當前格子的下一個狀態。當然最后別忘了將原始狀態傳遞出去。

題目要求

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?

這個內容在維基百科上講述的非常詳細，有圖文示例。
這個游戲玩家在游戲開始后是不能操作的，完全是由最初的狀態來決定最終的結果。板上的每個小格子有兩種狀態，live或dead。
而根據游戲規則，每一次這個板上的內容將會隨著前一次板上的內容發生變化。變化的規則如下：

如果當前格子為live，那么只要它周圍live鄰居的數量大于3個或是小于2個，該格子就會變成dead狀態。

如果當前個字為dead，那么只要它周圍live的鄰居數量正好為3個，該格子就會變成live狀態。否則還是dead狀態。

現在輸入一個狀態，讓我們更新出板子的下一個狀態。

思路和代碼

這里其實用暴力查詢的話也是可以解決的。也就是每遇到一個格子就將該格子的鄰居統統遍歷一下，計算一個鄰居里面live和dead的數量。然后再根據當前格子的狀態計算當前格子的下一個狀態。但是這里需要一個新的m*n的數組來保存新的狀態，有點浪費空間。而且不能很好的利用之前的遍歷結果。所以我們可以將之前的遍歷結果用某種方式直接存到當前的格子里，減少一些遍歷次數。

假設現在有這樣的一個board：

[
 [1,0,1],
 [0,0,1],
 [1,1,0],
]

我們從左上角開始遍歷，我們發現它的周圍一個live的鄰居都沒有，因此它的狀態將會變為0。但是與此同時，它的上一個狀態為1，需要傳遞給周圍的鄰居，因此我們可以采用將周圍鄰居+10的方式傳遞。如下：

[
 [0,10,1],
 [10,10,1],
 [1,1,0],
]

這是我們再看坐標為(0,1)的格子。假設當前個字上的值為cur，那么cur/10則是之前鄰居的數量，cur%10則代表該格子的初始狀態。根據這個規律，我們可以知道當前格子上的初始狀態為0即dead，而之前遍歷過的鄰居有1個。這時我們就無需遍歷所有的鄰居，只需要繼續訪問還未訪問的鄰居即可。當然最后別忘了將原始狀態傳遞出去。

代碼如下：

    public void gameOfLife(int[][] board) {
       if(board==null || board.length==0) return;
       int row = board.length;
       int column = board[0].length;
       int multiply = 10;
       for(int i = 0 ; i=0 && isLive(board[i+1][j-1])){liveNeighboars++;}
                   if(j+13){
                       board[i][j] = 0;
                   }else{
                       board[i][j] = 1;
                   }
                   if(j+1=0 && i+1

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 game-of-life Leetcod LeetCode Life

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68653.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
289. Life of Game

摘要：問題解答我的解法是需要最多的空間的。如果要做到那么我看到里一個非常的做法是用一個的數表示改變前和改變后的狀態。問題：According to the Wikipedias article: The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathem...

chuyao 2019-08-14 16:31 評論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
[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
Python+Pygame實操之玩命吃水果游戲的完成

　　吃豆人和削蘋果這兩個游戲想必大家都知道吧，本文運用Python里的Pygame控制模塊編寫出一個融合吃豆人+切水果的新手游：玩命吃蘋果，有興趣的話可以認識一下　　引言　　哈哈哈！木木子今天浮現——早已來給大家看了不少具體內容啦~　　涉及到的人工智能、新手、網絡爬蟲、數據統計分析（這一塊的通常但是審批）手機游戲...　　PS:　　吃豆人我寫過了哈　　Python+Pygame實戰之吃豆豆游戲的實...

89542767 2022-12-25 20:26 評論0 收藏0