超时程序
#include<stdio.h> #include<string.h> const int MAXN=100000; char ch[3][MAXN]; int d[MAXN][10][10]; int C[10][3][3]={0,1,0, 1,0,1, 1,1,1, 0,0,0, 0,0,1, 0,0,1, 0,1,0, 0,1,1, 1,1,0, 0,1,0, 0,1,1, 0,1,1, 0,0,0, 1,1,1, 0,0,1, 0,1,0, 1,1,0, 0,1,1, 0,1,0, 1,1,0, 1,1,1, 0,1,0, 0,0,1, 0,0,1, 0,1,0, 1,1,1, 1,1,1, 0,1,0, 1,1,1, 0,1,1 }; int tmp[3][5]; int num[10][10]; int fun1(int x,int y) { int i,j; int cnt,s; memset(tmp,0,sizeof(tmp)); for(i=0;i<3;i++) { for(j=0;j<3;j++) { tmp[i][j]=C[x][i][j]; } } for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(C[y][i][j]) tmp[i][j+2]=1; } } cnt=1,s=0; for(i=0;i<3;i++) { for(j=0;j<5;j++) { if(tmp[i][j]) { s+=cnt; } cnt*=2; } } return s; } int fun2(int x,int y,int m) { int i,j; memset(tmp,0,sizeof(tmp)); for(i=0;i<3;i++) { for(j=0;j<3;j++) { tmp[i][j]=C[x][i][j]; } } for(i=0;i<3;i++) { for(j=0;j<3;j++) { if(C[y][i][j]) tmp[i][j+2]=1; } } for(i=0;i<3;i++) { if(C[m][i][2]) { tmp[i][0]=1; } } int cnt=1,s=0; for(i=0;i<3;i++) { for(j=0;j<5;j++) { if(tmp[i][j]) { s+=cnt; } cnt*=2; } } return s; } int main() { int T,n; int i,j,k,ok,m; int cnt,s; for(i=0;i<10;i++) { for(j=0;j<10;j++) { num[i][j]=fun1(i,j); } } scanf("%d",&T); while(T--) { scanf("%d",&n); getchar(); gets(ch[0]); gets(ch[1]); gets(ch[2]); for(i=0;i<3;i++) { for(j=0;j<2*n+1;j++) { if(ch[i][j]!=' ' && ch[i][j]!='_' && ch[i][j]!='|') ch[i][j]=' '; } } if(n==0) { printf("0\n"); continue; } if(n==1) { ok=0; for(k=0;k<10;k++) { cnt=1; for(i=0;i<3 && cnt;i++) { for(j=0;j<3 && cnt;j++) { if( !( (ch[i][j]!=' ' && C[k][i][j]) || (ch[i][j]==' ' && !C[k][i][j]) ) ) { cnt=0; } } } if(cnt) { ok++; break; } } if(ok) printf("1\n"); else printf("0\n"); continue; } for(i=2;i<=n;i++) { for(j=0;j<10;j++) { for(k=0;k<10;k++) { d[i][j][k]=0; } } } for(k=2;k<=n;k++) { cnt=1,s=0; for(i=0;i<3;i++) { for(j=k*2-4;j<2*k+1;j++) { if(ch[i][j]!=' ') { s+=cnt; // printf("%d %d\n",cnt,s); } cnt*=2; } } if(k==2) { ok=0; for(i=0;i<10;i++) { for(j=0;j<10;j++) { if(num[i][j]==s) { d[k][j][i]=(d[k][j][i]+1)%1000000007; ok=1; } } } if(!ok) { printf("0\n"); break; } } else { ok=0; for(i=0;i<10;i++) { for(j=0;j<10;j++) { for(m=0;m<10;m++) { if(fun2(i,j,m)==s) { d[k][j][i]=(d[k][j][i]+d[k-1][i][m])%1000000007; ok=1; } } } } } } if(!ok) continue; s=0; for(i=0;i<10;i++) { for(j=0;j<10;j++) s=(s+d[n][i][j])%1000000007; } printf("%d\n",s); } return 0; }