自动搬运

查看原文

来自洛谷，原作者为

	lllyyykkk 给岁月以文明，而非给文明以岁月

搬运于2025-08-24 22:10:57，当前版本为作者最后更新于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;
}