題目：生命游戲
根據 百度百科 ，生命游戲，簡稱為生命，是英國數學家約翰·何頓·康威在 1970 年發明的細胞自動機，
給定一個包含 m × n 個格子的面板，每一個格子都可以看成是一個細胞，每個細胞都具有一個初始狀態：1 即為活細胞（live），或 0 即為死細胞（dead），每個細胞與其八個相鄰位置（水平，垂直，對角線）的細胞都遵循以下四條生存定律：
- 如果活細胞周圍八個位置的活細胞數少于兩個，則該位置活細胞死亡；
- 如果活細胞周圍八個位置有兩個或三個活細胞，則該位置活細胞仍然存活；
- 如果活細胞周圍八個位置有超過三個活細胞，則該位置活細胞死亡；
- 如果死細胞周圍正好有三個活細胞，則該位置死細胞復活；
根據當前狀態，寫一個函式來計算面板上所有細胞的下一個（一次更新后的）狀態，下一個狀態是通過將上述規則同時應用于當前狀態下的每個細胞所形成的，其中細胞的出生和死亡是同時發生的，
示例：
輸入：
[
[0,1,0],
[0,0,1],
[1,1,1],
[0,0,0]
]
輸出：
[
[0,0,0],
[1,0,1],
[0,1,1],
[0,1,0]
]
進階：
你可以使用原地演算法解決本題嗎？
請注意，面板上所有格子需要同時被更新：你不能先更新某些格子，然后使用它們的更新后的值再更新其他格子，
本題中，我們使用二維陣列來表示面板，原則上，面板是無限的，但當活細胞侵占了面板邊界時會造成問題，你將如何解決這些問題？
本題的難點在于如果直接更新原來的陣列的話，是會影響到其他位置的細胞的，題目要求要同時更新，
我們可以復制出來一個模板，這個模板用來記錄每個位置在這一狀態時候相鄰格子的細胞數，
通過這個模板，我們就可以去修改原陣列，并且符合同時更新的要求，
上代碼(c)：
void gameOfLife(int** board, int boardSize, int* boardColSize){ int f[8][2] = { {-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1} };//八個方向 int hang = boardSize; int lie = *boardColSize; int tmp[hang+1][lie+1]; memset( tmp, 0, sizeof(tmp) );
//統計周圍的細胞總數 for ( int i = 0; i <= hang; i++ ) for ( int j = 0; j <= lie; j++ ) { for( int z = 0; z < 8; z++ ) { int x = i + f[z][0]; int y = j + f[z][1]; if( x >= 0&& x < hang&& y >= 0&& y < lie&& board[x][y] == 1 ) tmp[i][j]++; } }
//修改原陣列 for( int i = 0; i < hang; i++ ) for( int j = 0; j < lie; j++ ) { if( board[i][j] == 1 ) { if( tmp[i][j] < 2|| tmp[i][j] > 3 ) board[i][j] = 0; } else { if( tmp[i][j] == 3 ) board[i][j] = 1; } } }
2020-04-0214:30:15
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/38527.html
標籤：C
上一篇：圖的深度優先搜索dfs