思路：使用A*算法的搜索
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<map> #include<cmath> #include<queue> #include<cstring> #include<set> #include<stack> #include<string> #include<ctime> #define LL long long #define u64 unsigned long long #define maxn 50010 #define mod 1000000007 #define INF 0x3f3f3f3f #define eps 1e-6 using namespace std; struct node { int mat[3][3],dis ; int x,y,h; u64 get() { u64 ans=0,tt=1; for( int i = 0 ; i < 3 ;i++) for( int j = 0 ;j < 3 ;j++) { ans += tt*mat[i][j] ; tt *= 9 ; } return ans ; } bool operator<(const node &s) const { return dis+h > s.dis+s.h || (dis+h==s.dis+s.h && dis > s.dis) ; } }; set<u64>ss; void find(int &x,int &y,node a) { for(int i = 0 ; i < 3 ;i++ ) for(int j = 0 ; j < 3 ;j++)if(!a.mat[i][j]) { x=i;y=j; return ; } } priority_queue<node>q; int get(node a,node b) { int ans=0; for(int i = 0 ; i < 3 ;i++ ) for(int j = 0 ; j < 3 ;j++) { if(a.mat[i][j] != b.mat[i][j] ) ans++ ; } return ans; } int bfs(node a,node b) { u64 ans=b.get(),tt=a.get(); if(ans==tt) return 0; node aa,bb; a.h=get(a,b) ; while(!q.empty())q.pop(); q.push(a) ; ss.clear(); ss.insert(tt) ; int x,y,i,hehe=9999; while(!q.empty()) { bb=q.top();q.pop(); tt=bb.get(); if(tt==ans) return bb.dis; x=bb.x; y=bb.y; if(x>0) { aa=bb; swap(aa.mat[x-1][y],aa.mat[x][y]) ; tt=aa.get(); if(!ss.count(tt)) { aa.x=x-1; aa.dis++ ; aa.h=get(aa,b) ; q.push(aa) ; ss.insert(tt) ; } } if(x<2) { aa=bb; swap(aa.mat[x+1][y],aa.mat[x][y]) ; tt=aa.get(); if(!ss.count(tt)) { aa.x=x+1; aa.dis++ ; aa.h=get(aa,b) ; q.push(aa) ; ss.insert(tt) ; } } if(y>0) { aa=bb; swap(aa.mat[x][y-1],aa.mat[x][y]) ; tt=aa.get(); if(!ss.count(tt)) { aa.y=y-1; aa.dis++ ; aa.h=get(aa,b) ; q.push(aa) ; ss.insert(tt) ; } } if(y<2) { aa=bb; swap(aa.mat[x][y+1],aa.mat[x][y]) ; tt=aa.get(); if(!ss.count(tt)) { aa.y=y+1; aa.dis++ ; aa.h=get(aa,b) ; q.push(aa) ; ss.insert(tt) ; } } if(y!=0&&x!=2) { aa=bb; swap(aa.mat[x+1][y-1],aa.mat[x][y]) ; tt=aa.get(); if(!ss.count(tt)) { aa.x=x+1; aa.y=y-1; aa.dis++ ; aa.h=get(aa,b) ; q.push(aa) ; ss.insert(tt) ; } } } return -1; } int main() { int i,j,n,m,k; int T; node a,b; cin >> T ; while(T--) { for( i= 0 ; i < 3 ;i++) for(j = 0; j < 3; j++) scanf("%d",&a.mat[i][j]) ; a.dis=0; find(i,j,a) ; a.x=i; a.y=j; for( i= 0 ; i < 3 ;i++) for(j = 0; j < 3; j++) scanf("%d",&b.mat[i][j]) ; b.dis=0; // int tt=clock(); printf("%d ",bfs(a,b)) ; // cout<<clock()-tt<<endl; } return 0 ; } /* 3 4 0 2 7 3 6 8 1 5 4 0 2 7 3 6 8 1 5 4 0 2 7 3 6 8 1 5 4 7 2 8 3 6 1 0 5 2 6 4 1 3 7 0 5 8 8 1 5 7 3 6 4 0 2 */