289. 生命游戏

题目

image-20240913145909533

解法

很简单的一道题目，很容易想到重新开辟一个相同大小的二维数组进行结果替换，但是这样就存在一个相对较大的额外空间复杂度，

建议使用新的变量来替代表示同时又不干扰别的内容运行。例如之前是1，下一个状态是0，就可以用4来表示，同理，0变成1 可以用3表示，最后再遍历一次将所有的变成 0 就可以了。因为简单，这里不给出代码

这段代码主要演示的是在一个二维数组中该如何对给定点位周围的点进行探查，使用数组预先处理好要变化的距离，判断越界情况后正常处理即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
pair<int, int> arr[8] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };


int FindOneNum(int i, int j, vector<vector<int>>& nums)
{
	int res = 0;
	int x = i, y = j;
    
    //使用数组来代替原本繁琐的if else
	for (auto it : arr)
	{
		x = i + it.first;
		y = j + it.second;
        
        //判断是否在范围内
		if (0 <= x && x < nums.size() && 0 <= y && y < nums[0].size() && nums[x][y] == 1)
		{
			++res;
		}

		x = i;
		y = j;
	}

	return res;

}

//需要返回一个值给res进行接受
int ChangLife(int i,int j,vector<vector<int>>& nums)
{
	int countOfOne = FindOneNum(i,j,nums);
	if (nums[i][j] == 1)
	{
		if (countOfOne < 2) return 0;
		else if (countOfOne >= 2 && countOfOne <= 3) return 1;
		else if (countOfOne > 3) return 0;

	}
	//死亡状态细胞
	else
	{
		if (countOfOne == 3) return 1;
		else return 0;
	}
}



void Array::gameOfLife(vector<vector<int>>& board)
{
	int m = board.size();
	int n = board[0].size();

	vector<vector<int>> res(m,vector<int>(n));

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			res[i][j] = ChangLife(i,j,board);
		}
	}

	board = res;
}