题意：
给一个3*N的矩阵，第一行和第三行可能会有地雷，第二行没有地雷，第二行每个格子上都有1个数，表示在以该格子为中心的九宫格中一共有几个地雷。
给出第二行每个格子上的数字，问安放地雷的方案。
思路：
乍一看不会。
然后再仔细想想，可以发现第一列的地雷数量决定了第二列的地雷数量，而第一列和第二列的数量决定了第三列的数量，由此可以进行如下递推。
由此总共三种情况，对第一列进行枚举，dp【i】表示第 i 列有几个地雷，详细内容见代码。
还有一点就是，在递推的时候可能会推出不符合实际的情况，出现这种情况的话，就需要令tmp = 0，因此每次递推结束之后都需要检验一遍。
代码：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int N = 1e4+100;
const int mod = 1e8+7;
char s[N];
int dp[N],num[N];
int x[10] = {1,2,1};
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",s);
int len = strlen(s);
rep(i,1,len)
{
num[i] = s[i-1]-'0';
}
int ans = 0;
rep(i,0,2)
{
if(i > num[1]) break;
int tmp = 1;
dp[1] = i;
tmp = tmp*x[i]%mod;
rep(j,2,len)
{
if(j == 2){
dp[j] = num[1]-dp[1];
if(dp[j] < 0 || dp[j] > 2) {tmp = 0; break;}
tmp = tmp*x[dp[j]]%mod;
}
else{
dp[j] = num[j-1]-dp[j-2]-dp[j-1];
if(dp[j] < 0 || dp[j] > 2) {tmp = 0; break;}
tmp = tmp*x[dp[j]]%mod;
}
}
dp[0] = 0, dp[len+1] = 0;
//检验程序：检验此种情况是否合法
rep(i,1,len)
{
if(num[i] != (dp[i]+dp[i-1]+dp[i+1])) {tmp = 0; break;}
}
ans = (ans+tmp)%mod;
}
printf("%d\n",ans);
}
return 0;
}
