双向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;
}
