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]]

解法

下面是使用C++实现“生命游戏”的代码，它根据给定的网格状态计算下一个状态：

#include <vector>
using namespace std;class Solution {
public:void gameOfLife(vector<vector<int>>& board) {int m = board.size();int n = board[0].size();// 创建一个方向数组来表示相邻的八个方向vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};// 遍历每个细胞，计算其下一个状态for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int liveNeighbors = 0;// 统计当前细胞周围的活细胞数for (auto dir : directions) {int ni = i + dir[0];int nj = j + dir[1];if (ni >= 0 && ni < m && nj >= 0 && nj < n && abs(board[ni][nj]) == 1) {liveNeighbors++;}}// 根据规则判断细胞的下一个状态if (board[i][j] == 1 && (liveNeighbors < 2 || liveNeighbors > 3)) {// 如果活细胞的邻居少于2个或多于3个，变成死细胞board[i][j] = -1;  // -1表示活细胞变成死细胞}if (board[i][j] == 0 && liveNeighbors == 3) {// 如果死细胞有正好3个邻居活细胞，复活board[i][j] = 2;  // 2表示死细胞变成活细胞}}}// 更新细胞的状态for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == -1) {board[i][j] = 0;  // -1变为0（死）} else if (board[i][j] == 2) {board[i][j] = 1;  // 2变为1（活）}}}}
};

代码说明：

1. 方向数组 directions: 用来表示每个细胞相邻的八个位置。
2. 邻居活细胞统计: 遍历每个细胞的八个相邻位置，统计活细胞的个数。
3. 规则判断:
   • 如果是活细胞且邻居活细胞少于2个或多于3个，则标记为死亡（暂时用-1表示）。
   • 如果是死细胞且正好有3个活细胞，则标记为复活（暂时用2表示）。
4. 状态更新: 将标记的状态（-1和2）更新回最终的状态（0或1）。

这个实现可以处理 m x n 大小的任意网格，时间复杂度为 O(m * n)，适用于一般规模的输入。

每一个各自去搜寻他周围的信息，肯定存在冗余，如何优化这个过程？

这是进一步的探索，目前实现方法就是遍历每一个。而如何遍历一个元素邻域也是个问题

如何遍历每一个元素的邻域？

 // 创建一个方向数组来表示相邻的八个方向vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

使用一个方向数组

方向数组如何表示方向？

在生命游戏的实现中，方向数组用来表示一个细胞的周围八个邻居的位置。方向数组中的 0 和 1 是通过表示相对的行和列偏移来确定方向的。

方向数组中的 0 和 1 解释

假设当前的细胞在网格中的位置是 (i, j)，我们可以通过对行 i 和列 j 进行加减操作来确定相邻的八个位置：

• {0, 1} 表示：行不变（0），列加1（1），即向右移动。
• {1, 0} 表示：行加1（1），列不变（0），即向下移动。
• {0, -1} 表示：行不变（0），列减1（-1），即向左移动。
• {-1, 0} 表示：行减1（-1），列不变（0），即向上移动。

这些偏移可以扩展到斜方向：

• {1, 1} 表示：行加1（1），列加1（1），即向右下角移动。
• {1, -1} 表示：行加1（1），列减1（-1），即向左下角移动。
• {-1, 1} 表示：行减1（-1），列加1（1），即向右上角移动。
• {-1, -1} 表示：行减1（-1），列减1（-1），即向左上角移动。

在遍历每个细胞时，我们可以根据这些方向数组中的偏移量来检查该细胞周围的邻居。例如，若当前细胞在位置 (i, j)，我们可以这样遍历其邻居：

int ni = i + dir[0];
int nj = j + dir[1];

使用行或列的平移操作

auto dir : directions这是什么用法

在 C++ 中，auto 是一种用于自动类型推导的关键字。它可以让编译器根据变量的初始值自动推导出该变量的类型，而不需要显式地声明类型。

在你的例子里，for (auto dir : directions) 使用了范围-based for 循环，auto 让编译器自动推导出 dir 的类型。directions 是一个二维的 vector<vector<int>>，其中每个元素是一个 vector<int>（表示一个方向）。因此，auto dir 实际上被推导为 vector<int> 类型。

详细说明：

for (auto dir : directions)

这个代码的意思是，依次遍历 directions 中的每一个元素，auto 让编译器自动推导出 dir 的类型。由于 directions 是 vector<vector<int>>，所以每一个 dir 实际上是一个 vector<int>，表示某一个方向（比如 {0, 1}，表示向右）。

使用 auto 的优点：

1. 减少代码冗长：不需要手动写出每个变量的确切类型，编译器可以自动推导。

   • 如果不用 auto，代码可能需要写成：

     for (vector<int> dir : directions)
     

     使用 auto 则更简洁：

     for (auto dir : directions)
     

2. 防止类型错误：在某些情况下，复杂类型的声明可能容易出错，使用 auto 可以让编译器直接根据上下文推导出正确的类型。

总结：
auto 是 C++11 引入的一种方便的特性，它让编译器根据上下文推导出变量的类型，减少了手动声明类型的繁琐，同时可以提高代码的可读性和可维护性。在你的代码中，auto 推导出的类型是 vector<int>。

board[i][j]一共有几种状态，为什么要设置这么多种，不是0和1代表生存和死亡就行？

多种状态的设置，就不需要再创建一个辅助矩阵来存储每个细胞的下一时刻过程。
且对于一个细胞，当前为1正存活，使用-1来表示它的未来状态，但是通过绝对值仍然可以获取当前状态，这是很精妙的地方
四种状态的含义
在这种实现中，board[i][j] 可以有四种状态：

0：当前是死细胞，下一状态也保持为死细胞。
1：当前是活细胞，下一状态也保持为活细胞。
-1：当前是活细胞，但下一状态变为死细胞。
2：当前是死细胞，但下一状态变为活细胞。

abs(board[ni][nj]) == 1

这个绝对值用的太妙了，直接减少了空间复杂度