A40836. 生命游戏
题目描述
生命游戏
题目描述
康威生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。
这个游戏在一个无限大的2D网格上进行。
初始时，每个小方格中居住着一个活着或死了的细胞。
下一时刻每个细胞的状态都由它周围八个格子的细胞状态决定。
具体来说：
1. 当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时， 该细胞变成死亡状态。（模拟生命数量稀少）
2. 当前细胞为存活状态时，当周围有2个或3个存活细胞时， 该细胞保持原样。
3. 当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）
4. 当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。 （模拟繁殖）
当前代所有细胞同时被以上规则处理后, 可以得到下一代细胞图。按规则继续处理这一代的细胞图，可以得到再下一代的细胞图，周而复始。
例如假设初始是:(X代表活细胞，.代表死细胞)
.....
.....
.XXX.
.....
下一代会变为:
.....
..X..
..X..
..X..
.....
康威生命游戏中会出现一些有趣的模式。例如稳定不变的模式：
....
.XX.
.XX.
....
还有会循环的模式：
...... ...... ......
.XX... .XX... .XX...
.XX... .X.... .XX...
...XX. -> ....X. -> ...XX.
...XX. ...XX. ...XX.
...... ...... ......
......
.XX...
.XX...
...XX.
...XX.
......
本题中我们要讨论的是一个非常特殊的模式，被称作"Gosper glider gun"：
......................................
.........................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代，请问第1000000000(十亿)代一共有多少活着的细胞？
注意：我们假定细胞机在无限的2D网格上推演，并非只有题目中画出的那点空间。
当然，对于遥远的位置，其初始状态一概为死细胞。
注意：需要提交的是一个整数，不要填写多余内容。
参考答案
ll x = 1e9;
void solve() {
// cout << "lll " << x / 10 << "\n";
ll sum = (x / 30) * 5;
x %= 30;
// cout << "x= " << x << "\n";
int s[30] = {3, 4, 5, 3, -7, 7, -3, 13, -19, 6, 2, 4, 1, 1, -14, 2, 3, 6, 1, 0, 0, -5, 11, -17, 7, -3, 0, 3, -2, -7};
int cnt = 0;
for (int i = 0; i < x; ++i)cnt += s[i];
// cout << cnt << " " << "jjj" << '\n';
sum += cnt + 36;//36为初始细胞数
cout << sum;
}答案解析
初始状态是第0代
细胞机在无限的2D网格上推演，并非只有题目中画出的那点空间
枚举十亿次是不现实的，应该相信是有循环规律的，或许到了第N代细胞机细胞数就不会变化，或许细胞数是一直增加的，但是增加得有规律。不管如何，都需要推演出这一代演化到下一代的细胞数目，这样才能探索出规律。判断一个活细胞或者死亡细胞的下一刻是否存活都是很简单的；难点是如何模拟无限的2D网格，用一个很庞大的数组也是不现实的，数组庞大，枚举量也会增大，而且到底用多大的数组仍然需要从原图去探索。数组不行，只能去寻找其他数据结构，Java中除了数组，第二种想到的应该是集合（List、Set、Map），如果通过集合来存取一张细胞机图中的所有X点（用一个类Point对象来代表活细胞，类成员变量x、y代表行、列），然后通过集合中的contains方法可以很轻松的判断一个活细胞周围的八个邻近细胞中有多少个存活细胞，从而判断出当前细胞的下一刻是否可以存活；活细胞判断完了，但是死亡细胞下一刻也有可能存活，茫茫多的死亡细胞如何判定？只要认识到只有在活细胞旁边的死亡细胞才有存活的可能性就知道了应用集合来解题是正确的，在统计一个活细胞旁边八个邻近的活细胞数目时，如果contains返回false，说明这个邻近细胞是死亡细胞，但是也说明了它是有存活的可能性的，所以此刻可以判断它周围的八个活细胞数目来判断其下一刻是否可以存活——每一个在活细胞周围的死亡细胞都应该这样一一去判断（需要注意的是，同一个死亡细胞可能存在不同的活细胞的周围，所以一个在将一个活过来的死亡细胞加入新的细胞机图时需要判断一下，否则可能会重复加入同一细胞）；这样遍历了一张细胞机图中所有的活细胞和有机会存活的死亡细胞后下一张新的细胞机图就会产生了；通过这样迭代，输出第N代前的每一代的细胞数目和代与代之间的细胞数目差来寻找规律。
答案：166666713