题解：P5457 [THUPC2018] 生生不息

lllyyykkk · 2025-01-03 20:34:12 · 题解

题目传送门

这是一道关于生命游戏的题目。 可以点击此处试玩。

思路

因为 n,m \le 5，且只是输入 n 与 m，考虑直接进行打表。 一个细胞在最好情况下的存活轮数应该不超过 60 轮，所以可以以 60 为上界。 但是 O(2^{nm}) 就是挂机也跑不出来，考虑进行优化。

显然，如果一个状态确定了是否合法，那么它前一个状态 和它就一定是一样的。 所以下一次遍历到这个状态就不必进行模拟了。

这显然可以用记忆化搜索实现。

用 map 压缩所有的状态，当一个状态被判定为是否合法后，将他的所有前置都判定掉，就可以了。

一个小优化：如果一次在压缩后和上次没有差别，就不用继续了。

打表代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans[6][6]={};
bool flag[6][6],vis[6][6];
int ssum[60];
int dx[8]={1,0,-1,0,1,1,-1,-1},dy[8]={0,-1,0,1,1,-1,1,-1};
map<int,int>mp;
inline int num(int x,int y){
    int sum=0;
    for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) sum=sum*2+vis[i][j];
    return sum;
}
inline bool check(int x,int y){
    int cnt=0;
    for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) vis[i][j]=flag[i][j];
    bool vvis[6][6];
    while(cnt<=60){
        bool dead=1;
        ssum[++cnt]=num(x,y);
        if(ssum[cnt]==ssum[cnt-1]&&cnt>1) return 1;
        if(mp[ssum[cnt]]==1){
            for(int i=cnt-1;i>=1;i--) mp[ssum[cnt]]=1;
            return 0;
        }
        if(mp[ssum[cnt]]==2){
            for(int i=cnt-1;i>=1;i--) mp[ssum[cnt]]=2;
            return 1;
        }
        for(int i=1;i<=x;i++){
            for(int j=1;j<=y;j++){
                int s=0;
                for(int d=0;d<8;d++){
                    int xx=i+dx[d],yy=j+dy[d];
                    if(xx<1||yy<1||xx>x||yy>y) continue;
                    s+=vis[xx][yy];
                }
                if(((s==2||s==3)&&vis[i][j])||((s==3)&&!vis[i][j])) vvis[i][j]=1,dead=0;
                else vvis[i][j]=0;
            }
        }
        if(dead){
            for(int i=cnt-1;i>=1;i--) mp[ssum[cnt]]=1;
            return 0;
        }
        for(int i=1;i<=x;i++) for(int j=1;j<=y;j++) vis[i][j]=vvis[i][j];
    }
    for(int i=cnt-1;i>=1;i--) mp[ssum[cnt]]=2;
    return 1;
}
void dfs(int pos,int x,int y){
    if(pos==x*y+1){
        int s=check(x,y);
        ans[x][y]+=s;   
        return;
    }
    int xx=pos/y+(pos%y?1:0),yy=pos%y;
    if(!yy) yy=y;
    flag[xx][yy]=0;
    dfs(pos+1,x,y);
    flag[xx][yy]=1;
    dfs(pos+1,x,y);
}
signed main(){
//  dfs(1,5,5);
    for(int i=1;i<=5;i++) for(int j=1;j<=5;j++) if(i!=5||j!=5) dfs(1,i,j),mp.clear();
    for(int i=1;i<=5;i++){
        cout <<'{'<<ans[i][1];
        for(int j=2;j<=5;j++) cout <<','<<ans[i][j];
        cout <<"},";
    }
    return 0;
}