HDU 5965 扫雷

题面

题解

枚举

一列的信息可以简并为其雷数，因为第二行的信息不区分第一行和第三行。

只要枚举第一列的雷数 (0,1,2) ，就可以根据第二行的八连通信息递推出每一列的雷数。

方案数就是雷数为 (1) 的列，枚举放在第一行或第三行，(2^k)

//https://acm.hdu.edu.cn/showproblem.php?pid=5965
//2021 10 20 nksbwen

#include <cstdio>
#include <cstring>

const int MAXN=100111;
const int MOD=100000007;

int sum(const int &a, const int &b){
	return a+b-((a+b>=MOD)?MOD:0);
}

int mul(const int &a, const int &b){
	return 1LL*a*b%MOD;
}

int pow(int a, int k){
	int r=1;
	while(k){
		if(k&1)	r=mul(r, a);
		a=mul(a, a);
		k>>=1;
	}
	return r;
}

int T;
int N;
char input[MAXN];
int Cnt[MAXN];
int S[MAXN];

int Calc(){
	int c=0;
	for(int i=1;i<=N;++i)	c+=Cnt[i]==1;
	return pow(2, c);
}

int main(){
	
	
	scanf("%d", &T);
	
	int Ans;
	bool flag;
	while(T--){
		scanf("%s", input);
		N=strlen(input);
		for(int i=1;i<=N;++i)	S[i]=input[i-1]-'0';
		Ans=0;
		flag=true;
		Cnt[1]=0;
		for(int i=1;i<=N;++i)	Cnt[i+1]=S[i]-Cnt[i]-Cnt[i-1];
		for(int i=1;i<=N;++i)	flag&=(Cnt[i+1]>=0 && Cnt[i+1]<=2);
		flag&=Cnt[N+1]==0;
		if(flag)	Ans=sum(Ans, Calc());
		
		flag=true;
		Cnt[1]=1;
		for(int i=1;i<=N;++i)	Cnt[i+1]=S[i]-Cnt[i]-Cnt[i-1];
		for(int i=1;i<=N;++i)	flag&=(Cnt[i+1]>=0 && Cnt[i+1]<=2);
		flag&=Cnt[N+1]==0;
		if(flag)	Ans=sum(Ans, Calc());
		
		flag=true;
		Cnt[1]=2;
		for(int i=1;i<=N;++i)	Cnt[i+1]=S[i]-Cnt[i]-Cnt[i-1];
		for(int i=1;i<=N;++i)	flag&=(Cnt[i+1]>=0 && Cnt[i+1]<=2);
		flag&=Cnt[N+1]==0;
		if(flag)	Ans=sum(Ans, Calc());
		printf("%d
", Ans);
	}
	
	return 0;
}