Lvat_s Blog

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