双向BFS
怎么写着写着就5kb+了呢……其他人为什么跑得那么快……
#include<cstdio> #include<cstdlib> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int Smod=9973; const pair<int,int> tab[]={make_pair(-1,-2),make_pair(-2,-1),make_pair(-1,2),make_pair(-2,1),make_pair(1,-2),make_pair(2,-1),make_pair(1,2),make_pair(2,1)}; const long long Lmod1=233333333333333ll,Lmod2=666666666666667ll; int T,hn1,hn2,mat[10][10],h1[10005],h2[10005]; char mt[10][10]; struct Hash{ int next,step; long long L1,L2; }ha1[1000005],ha2[1000005]; void AddHash1(int s,long long l1,long long l2,int step){ ha1[++hn1].L1=l1; ha1[hn1].L2=l2; ha1[hn1].step=step; ha1[hn1].next=h1[s]; h1[s]=hn1; } int FindHash1(int s,long long l1,long long l2){ for(int i=h1[s];i;i=ha1[i].next){ if(ha1[i].L1==l1 && ha1[i].L2==l2)return i; } return 0; } void AddHash2(int s,long long l1,long long l2,int step){ ha2[++hn2].L1=l1; ha2[hn2].L2=l2; ha2[hn2].step=step; ha2[hn2].next=h2[s]; h2[s]=hn2; } int FindHash2(int s,long long l1,long long l2){ for(int i=h2[s];i;i=ha2[i].next){ if(ha2[i].L1==l1 && ha2[i].L2==l2)return i; } return 0; } struct Matrix{ int mt[6][6],now; friend bool operator==(Matrix A,Matrix B){ for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++)if(A.mt[i][j]!=B.mt[i][j])return 0; } return 1; } }Template; pair<int,pair<long long,long long> > GetHash(Matrix M){ int s=0; long long l1=0,l2=0; for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ s=(s*127+M.mt[i][j])%Smod; l1=(l1*233+M.mt[i][j])%Lmod1; l2=(l2*667+M.mt[i][j])%Lmod2; } } return make_pair(s,make_pair(l1,l2)); } queue<Matrix> Q1,Q2; void OutMatrix(Matrix M){ puts("This is Mt:"); for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ printf("%d",M.mt[i][j]); } putchar('\n'); } puts("-------------"); } void BFS(int mode,int st){ if(st>8){puts("-1");return;} if(mode){ while(Q1.front().now==st){ Matrix u=Q1.front(); //OutMatrix(u); Q1.pop(); int x,y; for(x=1;x<=5;x++){for(y=1;y<=5;y++){if(!u.mt[x][y])break;}if(!u.mt[x][y] && y<6)break;} //printf("XY:%d %d\n",x,y); for(int i=0;i<8;i++){ int px=x+tab[i].first,py=y+tab[i].second,tc; if(px<1 || py<1 || px>5 || py>5)continue; swap(u.mt[x][y],u.mt[px][py]);u.now++; pair<int,pair<long long,long long> >Pt=GetHash(u); tc=FindHash2(Pt.first,Pt.second.first,Pt.second.second); if(tc){printf("%d\n",u.now+ha2[tc].step<=15?u.now+ha2[tc].step:-1);return;} tc=FindHash1(Pt.first,Pt.second.first,Pt.second.second); if(!tc){AddHash1(Pt.first,Pt.second.first,Pt.second.second,u.now);Q1.push(u);} swap(u.mt[x][y],u.mt[px][py]);u.now--; } } BFS(mode^1,st); return; } else { while(Q2.front().now==st){ Matrix u=Q2.front(); //OutMatrix(u); Q2.pop(); int x,y; for(x=1;x<=5;x++){for(y=1;y<=5;y++){if(!u.mt[x][y])break;}if(!u.mt[x][y] && y<6)break;} //printf("XY:%d %d\n",x,y); for(int i=0;i<8;i++){ int px=x+tab[i].first,py=y+tab[i].second,tc; if(px<1 || py<1 || px>5 || py>5)continue; swap(u.mt[x][y],u.mt[px][py]);u.now++; pair<int,pair<long long,long long> >Pt=GetHash(u); tc=FindHash1(Pt.first,Pt.second.first,Pt.second.second); if(tc){printf("%d\n",u.now+ha1[tc].step<=15?u.now+ha1[tc].step:-1);return;} tc=FindHash2(Pt.first,Pt.second.first,Pt.second.second); if(!tc){AddHash2(Pt.first,Pt.second.first,Pt.second.second,u.now);Q2.push(u);} swap(u.mt[x][y],u.mt[px][py]);u.now--; } } BFS(mode^1,st+1); return; } } void MakeMt(Matrix &x){ for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ x.mt[i][j]=mat[i][j]; } } x.now=0; } void Prepare(){ mat[1][1]=2;mat[1][2]=2;mat[1][3]=2;mat[1][4]=2;mat[1][5]=2; mat[2][1]=1;mat[2][2]=2;mat[2][3]=2;mat[2][4]=2;mat[2][5]=2; mat[3][1]=1;mat[3][2]=1;mat[3][3]=0;mat[3][4]=2;mat[3][5]=2; mat[4][1]=1;mat[4][2]=1;mat[4][3]=1;mat[4][4]=1;mat[4][5]=2; mat[5][1]=1;mat[5][2]=1;mat[5][3]=1;mat[5][4]=1;mat[5][5]=1; } void First(){ while(!Q1.empty())Q1.pop(); while(!Q2.empty())Q2.pop(); memset(h1,0,sizeof(h1)); memset(h2,0,sizeof(h2)); hn1=0;hn2=0; } int main(){ freopen("1085.in","r",stdin); freopen("1085.out","w",stdout); scanf("%d",&T); Prepare(); MakeMt(Template); while(T--){ First(); scanf("%s %s %s %s %s",mt[1]+1,mt[2]+1,mt[3]+1,mt[4]+1,mt[5]+1); for(int i=1;i<=5;i++){ for(int j=1;j<=5;j++){ if(mt[i][j]=='0')mat[i][j]=1; else if(mt[i][j]=='1')mat[i][j]=2; else mat[i][j]=0; } } Matrix Tp; pair<int,pair<long long,long long> > Pr; MakeMt(Tp); if(Tp==Template){puts("0");continue;} Q1.push(Tp); Q2.push(Template); Pr=GetHash(Tp); AddHash1(Pr.first,Pr.second.first,Pr.second.second,0); Pr=GetHash(Template); AddHash2(Pr.first,Pr.second.first,Pr.second.second,0); BFS(1,0); } return 0; }