题目大意
有一个 1 维的扫雷游戏，每个格子用*表示有雷，用 0/1/2 表示无雷并且相邻格子中有 0/1/2 个雷。
给定一个仅包含?、*、0、1、2 的字符串 s，问有多少种方法将所有的?改为*/0/1/2 使其合法。
题目分析
因为题目没有特殊的限制，且向左的转移可以转为向右转移，因此我们可以按照从左到右的阶段进行动态规划。
设状态$f[i,j]$表示前$i$个格子，第$i$个格子的状态为$j$的方案数。
其中状态$j$表示的意义如下：
- $j=0$：当前格子为$0$
- $j=2$：当前格子为$2$
- $j=3$：当前格子为$*$
- $j=4$：当前格子为$1$，且这个$1$表示右方有雷
- $j=4$：当前格子为$1$，且这个$1$表示左方有雷
然后我们就可以转移了，处理一下限制关系即可。
注意边界是不可能存在向外指的$1$或$2$的。
代码
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
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
string s;
int n;
const LL mod=1000000007;
LL f[1000005][6];
int main() {
ios::sync_with_stdio(false);
cin>>s;
n=s.length();
s=' '+s;
if(s[1]=='?')f[1][0]=f[1][4]=f[1][3]=1;
if(s[1]=='*')f[1][3]=1;
if(s[1]=='0')f[1][0]=1;
if(s[1]=='1')f[1][4]=1;
for(int i=2; i<=n; i++)
if(s[i]=='?') {
f[i][0]=(f[i-1][0]+f[i-1][5])%mod;
f[i][3]=(f[i-1][4]+f[i-1][2]+f[i-1][3])%mod;
f[i][5]=f[i-1][3];
if(i<n) {
f[i][2]=f[i-1][3];
f[i][4]=(f[i-1][0]+f[i-1][5])%mod;
}
} else if(s[i]=='*')f[i][3]=(f[i-1][4]+f[i-1][2]+f[i-1][3])%mod;
else if(s[i]=='0')f[i][0]=(f[i-1][0]+f[i-1][5])%mod;
else if(s[i]=='1') {
f[i][4]=(f[i-1][0]+f[i-1][5])%mod;
f[i][5]=f[i-1][3];
} else if(s[i]=='2')f[i][2]=f[i-1][3];
printf("%lld\n",(f[n][0]+f[n][3]+f[n][5])%mod);
return 0;
}
|
