我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。输入格式 输入第一行包含九宫的初态，第二行包含九宫的终态。输出格式 输出最少的步数，如果不存在方案，则输出-1。样例输入12345678.
123.46758样例输出3样例输入13524678.
46758123.样例输出22
如果你对这道题一点思路也没有的话，，建议你看看我的这篇博客：hdu八数码题解，这里面有关于八数码问题的资料判断有无解问题：根据逆序数直接判断有无解，对于一个八数码，依次排列之后，每次是将空位和相邻位进行调换，研究后会发现，每次调换，逆序数增幅都为偶数，也就是不改变奇偶性，所以只需要根据初始和目标状态的逆序数正负判断即可。
HASH问题：根据的是康托展开
下面请看代码，代码中有注释：
#include <cstdio>#include <queue>#include <algorithm>#include <cstring> #define MAX 400000using namespace std ;int visited[MAX];int HASH[9]={1,1,2,6,24,120,720,5040,40320} ;int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}} ;int des[3][3];struct Node{int map[3][3] ;int x , y ;int hash ;int g , h , f;bool operator<(const Node &n1)const{//return h==n1.h ? (g>n1.g):(h>n1.h) ;return f!=n1.f?f>n1.f:h>n1.h ;}bool check(){if(x<0||y<0 || x>=3||y>=3){return false ;}return true ;}//求哈希码用到了康托展开 void getHash(){int oth[9] , k = 0 ;for(int i = 0 ; i < 3 ; ++i){for(int j = 0 ; j < 3 ; ++j){oth[k++] = map[i][j] ;}}hash = 0 ; for(int i = 0 ; i < 9 ; ++i){int k = 0 ; for(int j = 0 ; j < i ; ++j){if(oth[i]<oth[j]){k++;}}hash += k*HASH[i] ;}}//求两点之间曼哈顿距离 void getH(){int oth[9] , k = 0 ;h = 0 ;for(int i = 0 ; i < 3 ; ++i){for(int j = 0 ; j < 3 ; ++j){int m = 0 , n = 0;for(m = 0 ; m < 3 ; ++m){for(n = 0 ; n < 3 ; ++n){if(map[i][j] == des[m][n]){goto loop ;}}}loop:h += abs(m-i)+abs(n-j) ;}}}}end;//根据八数码的性质，，判断有无解 bool judge(Node start , Node end){int s[9] , st = 0 , et = 0 ,k = 0;for(int i = 0 ; i < 3 ; ++i){for(int j = 0 ; j < 3 ; ++j){s[k++] =start.map[i][j] ;}}for(int i = 0 ; i < 9 ; ++i){for(int j = 0 ; j < i ; ++j){if(s[i]&&s[j]&&s[i]<s[j]){st++;}}}k = 0 ;for(int i = 0 ; i < 3 ; ++i){for(int j = 0 ; j < 3 ; ++j){s[k++] = end.map[i][j] ;}}for(int i = 0 ; i < 9 ; ++i){for(int j = 0 ; j < i ; ++j){if(s[i]&&s[j]&&s[i]<s[j]){et++;}}}return !((st&1)^(et&1)) ;}int AStar(Node start){priority_queue<Node> que;que.push(start);while(!que.empty()){Node now = que.top();que.pop() ;if(now.hash == end.hash){return visited[now.hash] ;}for(int i = 0 ; i < 4 ; ++i){Node next=now ;next.x += dir[i][0];next.y += dir[i][1];if(!next.check())//坐标越界 {continue ;} swap(next.map[now.x][now.y],next.map[next.x][next.y]) ;next.getHash() ;if(visited[next.hash] == 0)//这个图未访问过 {next.getH();next.g++ ;next.f = next.g+next.h;visited[next.hash] = next.g ;que.push(next) ;}else{if(next.g+1<visited[next.hash]) //如果这个图访问过，，但是现在访问代价更小，，则更新对该图的访问代价 {next.getH();next.g++ ;next.f = next.g+next.h;visited[next.hash] = next.g ;que.push(next) ;}}}}return -1 ;}int main(){char line[15];while(gets(line)){Node start;memset(visited,0,sizeof(visited)) ;for(int i = 0 ; i < 9 ; ++i){if(line[i] != '.')start.map[i/3][i%3] = line[i]-'0' ;else{start.map[i/3][i%3] = 0 ;start.x = i/3 , start.y = i%3 ;}}gets(line);for(int i = 0 ; i < 9 ; ++i){if(line[i] != '.')end.map[i/3][i%3] = line[i]-'0' ;elseend.map[i/3][i%3] = 0 ;if(line[i] != '.')des[i/3][i%3] = line[i]-'0' ;elsedes[i/3][i%3] = 0 ;}end.getHash() ;end.g = -1;end.getH();end.f = end.g+end.h ;start.getHash() ;start.getH() ;start.g = 0 ;start.f = start.g+start.h ;visited[start.hash] == 1; if(!judge(start,end)){printf("-1\n") ;continue ;}if(start.hash == end.hash){printf("0\n") ;continue ;}int ans = AStar(start) ;printf("%d\n",ans) ;}return 0;}