生命游戏 ### 题目描述 **本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。** 康威生命游戏是英国数学家约翰·何顿·康威在 $1970$ 年发明的细胞自动机。 这个游戏在一个无限大的 $2D$ 网格上进行。 初始时，每个小方格中居住着一个活着或死了的细胞。 下一时刻每个细胞的状态都由它周围八个格子的细胞状态决定。 具体来说： 1. 当前细胞为存活状态时，当周围低于 $2$ 个（不包含 $2$ 个）存活细胞时， 该细胞变成死亡状态。（模拟生命数量稀少） 2. 当前细胞为存活状态时，当周围有 $2$ 个或 $3$ 个存活细胞时， 该细胞保持原样。 3. 当前细胞为存活状态时，当周围有 $3$ 个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多） 4. 当前细胞为死亡状态时，当周围有 $3$ 个存活细胞时，该细胞变成存活状态。 （模拟繁殖） 当前代所有细胞同时被以上规则处理后, 可以得到下一代细胞图。按规则继续处理这一代的细胞图，可以得到再下一代的细胞图，周而复始。 例如假设初始是:( X 代表活细胞，. 代表死细胞) ```txt ..... ..... .XXX. ..... ``` 下一代会变为: ```txt ..... ..X.. ..X.. ..X.. ..... ``` 康威生命游戏中会出现一些有趣的模式。例如稳定不变的模式： ```txt .... .XX. .XX. .... ``` 还有会循环的模式： ```txt ...... ...... ...... .XX... .XX... .XX... .XX... .X.... .XX... ...XX. -> ....X. -> ...XX. ...XX. ...XX. ...XX. ...... ...... ...... ``` 本题中我们要讨论的是一个非常特殊的模式，被称作"Gosper glider gun"： ```txt ...................................... .........................X............ .......................X.X............ .............XX......XX............XX. ............X...X....XX............XX. .XX........X.....X...XX............... .XX........X...X.XX....X.X............ ...........X.....X.......X............ ............X...X..................... .............XX....................... ...................................... ``` 假设以上初始状态是第 $0$ 代，请问第 $10^9$ 代一共有多少活着的细胞？ 注意：我们假定细胞机在无限的 $2D$ 网格上推演，并非只有题目中画出的那点空间。当然，对于遥远的位置，其初始状态一概为死细胞。