题目链接：The Game of Life
题目大意：
一个无限大的平面网格上有一堆点，初始只分布在3*5的区域里面。
经过321次传递，每次传递遵从以下规则。
1.如果一个点是1，并且周围3*3的去心区域中有2或者3个1，那么这个点保留，否则去除。
2.如果一个点是0，并且周围3*3的去心区域中有3个1，那么这个点变成1。
询问每一次传递后有多少个1。
看着就像模拟，因为实在没啥规律，考虑每次最多向外传递一格，于是理论上642*642的方阵就够用了。
写了个暴力更新，于是愉快地T了。
后来发现其实到一定程度了就往外传递不了了，于是改成100*100，还是T了。
写了好久不知道咋做，只能去看提交列表里面的大哥做法。
看完直呼妙啊。
考虑邻接矩阵和邻接表的关系。
642*642的矩阵可以看成是邻接矩阵，但是这个范围实在是太大了，而且又很多0元素。
于是我们可以存储离散点，就类似于邻接表了，每次遍历的范围从坐标范围相关改成离散点个数相关，又因为有很多0元素，其实离散点个数很少。
就可以大幅度减小时间和空间占用了。
用一个vector存储当前在图上的点，对于每个点，在每次更新时都将它周围8个点丢到tmp数组中，排序去重，算出每个相同坐标重复的个数，就可以进行更新了。
当然还要储存每个点是否为1，这可以用map做到。
具体实现看代码
1 #include <bits/stdc++.h> 2 #define pii pair<int, int> 3 #define Mid ((l + r) / 2) 4 #define lson (rt << 1) 5 #define rson (rt << 1 | 1) 6 using namespace std; 7 int read() { 8 char c; int num, f = 1; 9 while(c = getchar(),!isdigit(c)) if(c == '-') f = -1; num = c - '0'; 10 while(c = getchar(), isdigit(c)) num = num * 10 + c - '0'; 11 return f * num; 12 } 13 int n, m; 14 vector<pii> vis, g, tmp; 15 map<pii, int> tt; 16 void evl() { 17 vis.clear(); tmp.clear(); 18 tt.clear(); 19 for(auto &t : g) { 20 tt[t] = 1; 21 for(int i = -1; i <= 1; i++) { 22 for(int j = -1; j <= 1; j++) if(i || j) { 23 vis.push_back({t.first + i, t.second + j}); 24 } 25 } 26 } 27 sort(vis.begin(), vis.end()); 28 for(int i = 0; i < vis.size(); i++) { 29 int k = 1; 30 while(i + k < vis.size() && vis[i + k] == vis[i + k - 1])k++; 31 if(k == 3 || (k == 2 && tt[vis[i]])) tmp.push_back({vis[i].first, vis[i].second}); 32 i = i + k - 1; 33 } 34 g = tmp; 35 } 36 void work() { 37 n = read(); m = read(); 38 g.clear(); 39 for(int i = 1; i <= n; i++) { 40 char s[10]; 41 scanf("%s", s + 1); 42 for(int j = 1; j <= m; j++) { 43 if(s[j] == '#') 44 g.push_back({i, j}); 45 } 46 } 47 int k = 0, tmp = g.size(); 48 for(int qwq = 1; qwq <= 321; qwq++) { 49 evl(); 50 if((int)g.size() > tmp) { 51 tmp = g.size(); 52 k = qwq; 53 } 54 } 55 printf("%d %d %d ", k, tmp, (int)g.size()); 56 } 57 signed main() 58 { 59 int Case = read(); 60 while(Case--) work(); 61 return 0; 62 }