HDU 5965 扫雷

发表于 | 分类于 | 评论数：

摘要

$3*n$ 扫雷，中间行已知且无雷，求合法布雷方案数。

枚举一下第一列雷的个数，递推。

题面

题解

枚举

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//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\n", Ans);
	}
	
	return 0;
}