leetcode_289生命游戏

289. 生命游戏

难度中等

根据百度百科，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1：

输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

示例 2：

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 为 0 或 1

int rowStep[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int colStep[8] = {-1, 0, 1, -1, 1, -1, 0, 1};


// 如需使用华为安全函数，请加上 #include "securec.h"
int CountNearCell(int **board, int r, int rSize, int c, int cSize) {
	int cnt = 0;
	for(int i = 0; i < 8; i++) {
		if((r + rowStep[i] < 0) || (r + rowStep[i] >= rSize) || (c +colStep[i] < 0) || (c + colStep[i] >= cSize) ) {
			continue;
		}
		if(board[r + rowStep[i]][c + colStep[i]] == 1) {
			cnt++;
		}
	}
	return cnt;
}



//如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
//如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
//如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
//如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

void gameOfLife(int** board, int boardSize, int* boardColSize){
	//boardSize 为行个数
	//*boardColSize 存的是对应行的列的个数，本题每列的个数一样，直接取 boardColSize[0] 
	int  i = 0;
	int  j = 0;
	int **res = (int **)malloc(sizeof(int *) * boardSize);
	memset(res, 0, sizeof(int *) * boardSize);

	for(i = 0; i < boardSize; i++) {
		res[i] =(int *)malloc(sizeof(int) * boardColSize[0]);
		memset(res[i], 0, sizeof(int) * boardColSize[0]);

		//res[i] = tmp;
		for(j = 0; j < boardColSize[0]; j++) {
			int cellnum = CountNearCell(board, i, boardSize, j, boardColSize[0]);
			if(cellnum < 2) {
				res[i][j]  = 0;
			} else if(cellnum  == 2) {
				res[i][j] = board[i][j];
			} else if(cellnum == 3) {
				res[i][j] = 1;
			} else if(cellnum > 3) {
				res[i][j] = 0;
			}
		}
	}
	memcpy(board, res, sizeof(int *) * boardSize);
	return ;
}

int rowStep[8] = {-1, -1, -1, 0, 0, 1, 1, 1};int colStep[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

// 如需使用华为安全函数，请加上 #include "securec.h"int CountNearCell(int **board, int r, int rSize, int c, int cSize) {int cnt = 0;for(int i = 0; i < 8; i++) {if((r + rowStep[i] < 0) || (r + rowStep[i] >= rSize) || (c +colStep[i] < 0) || (c + colStep[i] >= cSize) ) {continue;}if(board[r + rowStep[i]][c + colStep[i]] == 1) {cnt++;}}return cnt;}

//如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；//如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；//如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；//如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
void gameOfLife(int** board, int boardSize, int* boardColSize){//boardSize 为行个数//*boardColSize 存的是对应行的列的个数，本题每列的个数一样，直接取 boardColSize[0] int i = 0;int j = 0;int **res = (int **)malloc(sizeof(int *) * boardSize);memset(res, 0, sizeof(int *) * boardSize);
for(i = 0; i < boardSize; i++) {res[i] =(int *)malloc(sizeof(int) * boardColSize[0]);memset(res[i], 0, sizeof(int) * boardColSize[0]);
//res[i] = tmp;for(j = 0; j < boardColSize[0]; j++) {int cellnum = CountNearCell(board, i, boardSize, j, boardColSize[0]);if(cellnum < 2) {res[i][j] = 0;} else if(cellnum == 2) {res[i][j] = board[i][j];} else if(cellnum == 3) {res[i][j] = 1;} else if(cellnum > 3) {res[i][j] = 0;}}}memcpy(board, res, sizeof(int *) * boardSize);return ;}

16算法

leetcode_289生命游戏

289. 生命游戏

相关

标签