BFS+康托压缩

解题思路:

注意事项:

参考代码:

#include

using namespace std;

string s1,s2;

int a[5][5],b[5][5];

int jiecheng[10]={1,1,2,6,24,120,720,5040,40320,362880};

bool vis[363000];

int cod[10];

int nixvnum[10];

int x,y;//空格所在的坐标 

int endjvmian;

int mov[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

struct sit{

int a[5][5];

int x;

int y;

int step;

};

void debug(sit sit1){

cout<<"x="<<sit1.x<<"y="<<sit1.y<<"step="<<sit1.step<<endl;

for(int i=1;i<=3;i++){

for(int j=1;j<=3;j++){

cout<<sit1.a[i][j];

}

cout<<endl;

}

cout<<endl;

}

int Cantor(int tu[5][5]){

for(int i=1;i<=3;i++){

for(int j=1;j<=3;j++){

cod[(i-1)*3+j]=tu[i][j];

}

}

memset(nixvnum,0,sizeof(nixvnum));

for(int i=1;i<=8;i++){

for(int j=i+1;j<=9;j++){

if(cod[i]>cod[j])nixvnum[i]++;

}

}

int ret=0;

for(int i=1;i<=8;i++){

ret+=nixvnum[i]*jiecheng[9-i];

}

return ret;

}

void init(){

for(int i=1;i<=3;i++){

for(int j=1;j<=3;j++){

if(s1[(i-1)*3+j-1]=='.'){

x=i;y=j;

a[i][j]=9;

}

else a[i][j]=s1[(i-1)*3+j-1]-'0';

}

}

for(int i=1;i<=3;i++){

for(int j=1;j<=3;j++){

if(s2[(i-1)*3+j-1]=='.'){

b[i][j]=9;

}

else b[i][j]=s2[(i-1)*3+j-1]-'0';

}

}

endjvmian=Cantor(b);

}

int bfs(){

queue

sit now,nex;

int jvmian;

for(int i=1;i<=3;i++){

for(int j=1;j<=3;j++){

now.a[i][j]=a[i][j];

}

}

now.x=x;now.y=y;now.step=0;

jvmian=Cantor(now.a);

if(jvmian==endjvmian)return 0;

vis[jvmian]=1;

q.push(now);

while(!q.empty()){

now=q.front();q.pop();

//debug(now);

jvmian=Cantor(now.a);

for(int i=0;i<4;i++){

int x=now.x,y=now.y;

int x1=x+mov[i][0],y1=y+mov[i][1];

if(!(1<=x1&&x1<=3&&1<=y1&&y1<=3))continue;

swap(now.a[x][y],now.a[x1][y1]);

jvmian=Cantor(now.a);

swap(now.a[x][y],now.a[x1][y1]);

if(jvmian==endjvmian)return now.step+1;//已经到达终点 

if(vis[jvmian])continue;//这种局面已经访问过了

nex.x=x1;nex.y=y1;

nex.step=now.step+1;

memcpy(nex.a,now.a,sizeof(a));

swap(nex.a[x][y],nex.a[x1][y1]);

vis[jvmian]=1;

q.push(nex);

}

}

return -1; 

}

int main(){ 

ios::sync_with_stdio(false);

//debug();

cin>>s1;

cin>>s2;

init();

cout<<bfs();

}