题解：P17218 [ICPC 2017 Nanning R] The Game of Life

Super_Diu · 2026-08-09 20:55:34 · 题解

思路：只维护活细胞集合，不模拟无限网格。

因为初始活细胞最多只有 3\times 5=15 个，而每个细胞下一代只可能由它自己或它的 8 个邻居产生，所以每代只要统计当前活细胞和它的 8 个邻居就够了。

并且数据范围很小，所以直接模拟即可。

• 用 set 维护活细胞点集。

• 循环 1 到 321 代：

  • 把当前全部活细胞点 (x,y) 的 8 个邻居放入临时列表中。

  • 排序并统计活细胞个数 cnt（包含当前点）

  • 其他情况全部死亡。

  • 生成下一代活细胞集合，更新种群数量。

  • 更新最大值。

• 输出种群最大的那一代、最大种群中的活细胞个数和第 321 代的活细胞个数。

:::success[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
typedef long long ll;
using namespace std;
const int N=5+10;
int t;
int n,m;
char c;
set<pii> st;
inline bool have(const auto& s,const int& x,const int& y){
    return s.find({x,y})!=s.end();
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        st.clear();
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j){
                cin>>c;
                if(c=='#') st.insert({i,j});
            }
        int best=0,maxn=st.size();
        for(int r=1;r<=321;++r){
            vector<pii> cell;
            for(auto&[x,y]:st)
                for(int tx=-1;tx<=1;++tx)
                    for(int ty=-1;ty<=1;++ty)
                        cell.push_back({x+tx,y+ty});
            sort(cell.begin(),cell.end());
            set<pii> nxt;
            for(int i=0;i<cell.size();){
                int j=i;
                while(j<cell.size()&&cell[i]==cell[j]) j++;
                int cnt=j-i;
                auto&[x,y]=cell[i];
                if(cnt==3||cnt==4&&have(st,x,y))
                    nxt.insert({x,y});
                i=j;
            }
            st=nxt;
            int size=st.size();
            if(maxn<size){
                maxn=size;
                best=r;
            }
        }
        cout<<best<<' '<<maxn<<' '<<st.size()<<'\n';
    }
    return 0;
}

:::