题目描述：
有一个1维的扫雷游戏，每个格子用$*$表示有雷，用$0/1/2$表示无雷并且相邻格子中有$0/1/2$个雷。
给定一个仅包含$?、*、0、1、2$的字符串$s$，问有多少种方法将所有的$?$改为$*/0/1/2$使其合法。
输入格式：
一行个字符串$s$。
输出格式：
一行一个整数表示答案，对$1e9$ $+$ $7$取模
输入样例：
？1？
输出样例：
2
数据范围：
对于$100$$\%$的数据 $|s|$ $≤$ $10$6
思路：
定义$f[i][j]$表示$1$ ~ $i$中的$?$可以的填法，其中第$i$个字符为$j$的方案数。
其中$*$是$j$ $=$ $0$，$0$是$j$ $=$ $1$，$1$是$j$ $=$ $2$，$2$是$j$ $=$ $3$。
因为当$j$ $=$ $2$时，雷可以在左也可以在右，所以再定义$f[i][j][k]$，其中$i$和$j$与上文一样，当$j$ $=$ $1$时，$k$ $=$ $0$代表雷在i左的位置，$k$ $=$ $1$代表雷在$j$右的位置；其余情况$k$ $=$ $0$。
易得转移方程和边界条件，详见代码：
1 #include <bits/stdc++.h> 2 #define INF 0x3f3f3f3f 3 #define ll long long 4 using namespace std; 5 const ll MOD = 1e9 + 7; 6 char s[1000010]; 7 int l; 8 ll f[1000010][4][2]; 9 int main() 10 { 11 scanf("%s", s + 1); 12 l = strlen(s + 1); 13 if(s[1] == '*') f[0][2][1] = 1; 14 else if(s[1] == '?') f[0][2][1] = 1, f[0][1][0] = 1; 15 else f[0][1][0] = 1; 16 for(int i = 1; i <= l; ++i) 17 { 18 if(s[i] == '?') 19 { 20 f[i][0][0] = ((f[i - 1][0][0] + f[i - 1][2][1]) % MOD + f[i - 1][3][0]) % MOD; 21 f[i][1][0] = (f[i - 1][1][0] + f[i - 1][2][0]) % MOD; 22 f[i][2][0] = f[i - 1][0][0] % MOD; 23 f[i][2][1] = (f[i - 1][1][0] + f[i - 1][2][0]) % MOD; 24 f[i][3][0] = f[i - 1][0][0] % MOD; 25 } 26 else if(s[i] == '*') f[i][0][0] = ((f[i - 1][2][1] + f[i - 1][0][0]) % MOD + f[i - 1][3][0]) % MOD; 27 else if(s[i] == '0') f[i][1][0] = (f[i - 1][1][0] + f[i - 1][2][0]) % MOD; 28 else if(s[i] == '1') f[i][2][0] = f[i - 1][0][0] % MOD, f[i][2][1] = (f[i - 1][2][0] + f[i - 1][1][0]) % MOD; 29 else f[i][3][0] = f[i - 1][0][0] % MOD; 30 } 31 printf("%lld", ((f[l][0][0] + f[l][1][0]) % MOD + f[l][2][0]) % MOD); 32 return 0; 33 }