GroupBlog

扫雷游戏是晨晨和小璐特别喜欢的智力游戏，她俩最近沉迷其中无法自拔。
该游戏的界面是一个矩阵，矩阵中有些格子中有一个地雷，其余格子中没有地雷。游戏中，格子可能处于己知和未知的状态。如果一个己知的格子中没有地雷，那么该格子上会写有一个一位数，表示与这个格子八连通相邻的格子中地雷总的数量。
现在，晨晨和小璐在一个3行N列（均从1开始用连续正整数编号）的矩阵中进行游戏，在这个矩阵中，第2行的格子全部是己知的，并且其中均没有地雷；而另外两行中是未知的，并且其中的地雷总数量也是未知的。
晨晨和小璐想知道，第1行和第3行有多少种合法的埋放地雷的方案。

Input包含多组测试数据，第一行一个正整数T，表示数据组数。
每组数据由一行仅由数字组成的长度为N的非空字符串组成，表示矩阵有3行N 列，字符串的第i个数字字符表示矩阵中第2行第i个格子中的数字。
保证字符串长度N <= 10000，数据组数<= 100。
Output每行仅一个数字，表示安放地雷的方案数mod100,000,007的结果。 Sample Input

2
22
000

Sample Output

6
1

考虑这个时候对前两对两边点进行多种情况考虑，，其他的可以根据前两对的计算出来，，然后再验证正确性。

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef  vector<int> vi ;
typedef  long long ll;
typedef  unsigned long long  ull; 
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
#define MOD 100000007
int getnum(int x ,int y);

ll a[10005];
string s; 
int T;
int main()
{
	ios::sync_with_stdio(false);
	while(cin >> T)
	{
		while(T--)
		{
			int flag =0;
			ll re =0;
			s.clear();
			memset(a,0,sizeof(a));
			cin >> s;
			
			for(int i=0;i<s.size();i++)
			{
				if(s[i]>'6')
				{
					cout<<0<<endl;
					flag = 1;
					break;
				}
			} 
			if(flag)
			{
				continue;
			} 
			if(s[0]=='1')
			{
				re=(re+getnum(1,0))%MOD;
				re=(re+getnum(0,1))%MOD;
			} 
			else if(s[0]=='2')
			{
				re=(re+getnum(1,1))%MOD;
				re=(re+getnum(2,0))%MOD;
				re=(re+getnum(0,2))%MOD;
			}
			else if(s[0]=='3')
			{
				re=(re+getnum(2,1))%MOD;
				re=(re+getnum(1,2))%MOD;
			}
			else if(s[0]=='4')
			{
				re=(re+getnum(2,2))%MOD; 
			}
			else
			{
				re=(re+getnum(0,0))%MOD;
			}
			
			cout<<re<<endl;
		}
		
	}
	return 0;
} 

int getnum(int x ,int y)
{
	memset(a,0,sizeof(a));
	ll len = s.size();
	ll sum = 1;
	a[0] = x;
	a[1] = y;
	if(a[0]==1)
		sum=(sum*2)%MOD;
	if(a[1]==1)
		sum=(sum*2)%MOD;
	for(int i=1;i<=len-2;i++)
	{
		int tt =s[i]-'0'-a[i]-a[i-1];
		if(tt<0||tt>2)
		{
			return 0;
		}
		a[i+1] = tt;
		if(tt==1)
		{
			sum=(sum*2)%MOD;
		}
	}
	
	
	if(a[1]+a[0]+'0'!=s[0])
		sum = 0;
	if(a[len-1]+a[len-2]+'0'!=s[len-1])
		sum = 0;
		
	for(int i=1;i<len-2;i++)
	{
		if(a[i]+a[i-1]+a[i+1]+'0'!=s[i])
		{
			sum = 0;
			break;
		}		
	}
	
	
	
	return sum;			
}