丢个代码,就跑。。。暂时弃更。。。
#include<cstdio> #include<iostream> #include<cstring> #define MAXN 15 #define int long long using namespace std; int N,M; bool za[MAXN][MAXN]; char rn[MAXN]; int bin[15]; int ans=0,endx,endy; const int mo=299987; struct hhash{ int st,nt,val; }bl[2][14348907+10];int hd[2][mo+10],itot[2]; //14348907 shi 3^15 void insert(int st,int num,int knd){ int u=st%mo+1; bool ok=0; for(int i=hd[knd][u];i;i=bl[knd][i].nt) if(bl[knd][i].st==st){ bl[knd][i].val+=num; ok=1; break; } if(!ok){ bl[knd][++itot[knd]].st=st; bl[knd][itot[knd]].nt=hd[knd][u]; bl[knd][itot[knd]].val=num; hd[knd][u]=itot[knd]; } } signed main(){ // freopen("da.in","r",stdin); bin[0]=1; for(int i=1;i<=14;++i) bin[i]=bin[i-1]<<2; scanf("%lld%lld",&N,&M); for(int i=1;i<=N;++i){ scanf("%s",rn+1); for(int j=1;j<=M;++j) if(rn[j]=='.'){ za[i][j]=1; endx=i,endy=j; } } int now=1,past=0; insert(0,1,past); for(int i=1;i<=N;++i){ for(int s=1;s<=itot[past];++s) bl[past][s].st<<=2; for(int j=1;j<=M;++j){ //cout<<"QwQ"<<i<<" "<<j<<endl; memset(hd[now],0,sizeof(hd[now])); itot[now]=0; for(int s=1;s<=itot[past];++s){ int st=bl[past][s].st,num=bl[past][s].val; int b1=(st>>(2*(j-1)))%4,b2=(st>>(2*j))%4; //cout<<"orz"<<b1<<" "<<b2<<endl; if(!za[i][j]){ if(!b1&&!b2){ insert(st,num,now); } } else if(!b1&&!b2){ if(za[i+1][j]&&za[i][j+1]) insert(st+bin[j-1]+bin[j]*2,num,now); } else if(!b1&&b2){ if(za[i][j+1]) insert(st,num,now); if(za[i+1][j]) insert(st+b2*bin[j-1]-b2*bin[j],num,now); } else if(b1&&!b2){ if(za[i][j+1]) insert(st-b1*bin[j-1]+b1*bin[j],num,now); if(za[i+1][j]) insert(st,num,now); } else if(b1==1&&b2==1){ int dx=1; for(int k=j+1;k<=M;++k){ if((st>>(k*2))%4==1) ++dx; if((st>>(k*2))%4==2) --dx; if(!dx){ insert(st-bin[j-1]-bin[j]-bin[k],num,now); break; } } } else if(b1==2&&b2==2){ int dx=1; for(int k=j-2;k>=0;--k){ if((st>>(k*2))%4==2) ++dx; if((st>>(k*2))%4==1) --dx; if(!dx){ insert(st-2*bin[j-1]-2*bin[j]+bin[k],num,now); break; } } } else if(b1==2&&b2==1){ insert(st-2*bin[j-1]-bin[j],num,now); } else if(b1==1&&b2==2){ if(i==endx&&j==endy) ans+=num; } } now=past;past=now^1; } } printf("%lld\n",ans); } /* 0 wu cha tou 1 xia cha tou 2 you cha tou */
To be continued...