摘要:?jiǎn)栴}解答我的解法是需要最多的空間的。如果要做到那么我看到里一個(gè)非常的做法是用一個(gè)的數(shù)表示改變前和改變后的狀態(tài)。
問題:
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, Listlist) { 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里一個(gè)非常tricky的做法是用一個(gè)2-bit的數(shù)表示改變前和改變后的狀態(tài)。改變前有兩個(gè)狀態(tài):00, 01. 在滿足一定的條件后,改變前一個(gè)bit的狀態(tài)也有兩種:10, 11.所以我們只要記錄改變的狀態(tài),然后將實(shí)際的數(shù)向后移動(dòng)一位就可以得到當(dāng)然的一狀態(tài)。
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; } } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/66212.html
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 ...
摘要:板上的每個(gè)小格子有兩種狀態(tài),或。而根據(jù)游戲規(guī)則,每一次這個(gè)板上的內(nèi)容將會(huì)隨著前一次板上的內(nèi)容發(fā)生變化。然后再根據(jù)當(dāng)前格子的狀態(tài)計(jì)算當(dāng)前格子的下一個(gè)狀態(tài)。當(dāng)然最后別忘了將原始狀態(tài)傳遞出去。 題目要求 According to the Wikipedias article: The Game of Life, also known simply as Life, is a cellular...
摘要:思路普通解法,遍歷每一個(gè)細(xì)胞求值,用一個(gè)的矩陣存放結(jié)果。求值過程,稍微分析一下可知,其實(shí)就是按照以下的矩陣進(jìn)行結(jié)果是可數(shù)的。 According to the Wikipedias article: The Game of Life, also knownsimply as Life, is a cellular automaton devised by the Britishmath...
吃豆人和削蘋果這兩個(gè)游戲想必大家都知道吧,本文運(yùn)用Python里的Pygame控制模塊編寫出一個(gè)融合吃豆人+切水果的新手游:玩命吃蘋果,有興趣的話可以認(rèn)識(shí)一下 引言 哈哈哈!木木子今天浮現(xiàn)——早已來給大家看了不少具體內(nèi)容啦~ 涉及到的人工智能、新手、網(wǎng)絡(luò)爬蟲、數(shù)據(jù)統(tǒng)計(jì)分析(這一塊的通常但是審批)手機(jī)游戲... PS: 吃豆人我寫過了哈 Python+Pygame實(shí)戰(zhàn)之吃豆豆游戲的實(shí)...
摘要:如果多核的機(jī)器如何優(yōu)化因?yàn)槭嵌嗪耍覀兛梢杂镁€程來實(shí)現(xiàn)并行計(jì)算。如果線程變多分塊變多,邊緣信息也會(huì)變多,開銷會(huì)增大。所以選取線程的數(shù)量是這個(gè)開銷和并行計(jì)算能力的折衷。 Game of Life I According to the Wikipedias article: The Game of Life, also known simply as Life, is a cellula...
閱讀 632·2021-08-17 10:15
閱讀 1715·2021-07-30 14:57
閱讀 1971·2019-08-30 15:55
閱讀 2813·2019-08-30 15:55
閱讀 2704·2019-08-30 15:44
閱讀 662·2019-08-30 14:13
閱讀 2380·2019-08-30 13:55
閱讀 2588·2019-08-26 13:56