九宫填数(c++)代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#include<utility>

#include<map>

#include<stack>

#include<sstream>

#include<math.h>

#include<bitset>

#include<queue> 

#include<set>

using namespace std;

int mp[5][5];

int r[5][5];

int xx;

string s1;

string s2;

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

bool in(int x,int y){

return x>=0&&x<3&&y>=0&&y<3;

} 

struct node{

int k;

int dept;

string sk;

    node(int dk,int dd,string sss){

    k=dk;

    dept=dd;

    sk=sss;

    }

};

int bfs(int x){

queue<node>q;

q.push(node(x,0,s1));

set<string>cnt;

cnt.insert(s1);

while(!q.empty()){

node now=q.front();

q.pop();

int kx=now.k/3;

int ky=now.k-(kx*3);

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

int dx=kx+road[i][0];

int dy=ky+road[i][1];

int tk=3*dx+dy;

string tmp=now.sk;

    if(in(dx,dy)){

    tmp[now.k]=tmp[tk];

    tmp[tk]='.';

    if(cnt.find(tmp)==cnt.end()){

    if(tmp==s2){

    return now.dept+1;

    }

    cnt.insert(tmp);

    q.push(node(tk,now.dept+1,tmp));

    }

    }

} 

}

return -1;

}

int main(){

cin>>s1;

for(int i=0;i<s1.length();i++){

if(s1[i]=='.'){

xx=i;

}

}

cin>>s2;

int kk=bfs(xx);

cout<<kk<<endl;

return 0;

}