#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <set>

 #include <queue>

 #include <algorithm>

 #include <vector>

 #include <map>

 #include <time.h>

 using namespace std;

 struct Item        //每一个状态

 {

     int state[][];

     int Pre;    //父状态在path中的下标

     int F,G,H;    //估计函数 F=G+H

     Item(int state[][],int Pre,int G,int H)    //构造函数

     {

         this->Pre=Pre;

         this->G=G;

         this->H=H;

         this->F=G+H;

         for(int i=;i<;i++)

             for(int j=;j<;j++)

                 this->state[i][j]=state[i][j];

     }

     bool operator <(const Item temp) const        //运算符重载，用于priority_queue中元素的比较

     {

         return F>temp.F;

     }

     bool operator ==(const Item temp) const

     {

         for(int i=;i<;i++)

             for(int j=;j<;j++)

                 if(state[i][j]!=temp.state[i][j])    return ;

         return ;

     }

 };

 priority_queue<Item> Open;    //存储扩展出但还没有访问的表

 map<int,bool> Close;        //存储已经访问过的节点

 vector<Item> path;            //保存路径

 int arrays[][]={,,,,,,,,},arraye[][]={,,,,,,,,};    //八数码初始状态和目标状态

 int dx[]={,,-,},dy[]={,-,,};    //四个方向扩展

 int CalcuH(const int a0[][],const int a1[][])    //CalcuH（当前状态，目标状态）计算 H，如果目标状态和当前状态某个位置数字不同，dis自加1

 {

     int dis=;

     for(int i=;i<;i++)

         for(int j=;j<;j++)

             if(a0[i][j]!=a1[i][j])    dis++;

     return dis;

 }

 bool Judge(const int p0[][],const int p1[][])    //两者逆序数奇偶性相等,看八数码是否有解

 {

     int ss = , ee = ;

     for(int i=; i<; ++i)

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

             if(p0[j/][j%] !=  && p0[j/][j%] < p0[i/][i%]) ++ss;

             if(p1[j/][j%] !=  && p1[j/][j%] < p1[i/][i%]) ++ee;

         }

     return (ss&) == (ee&);

 }

 int GetIndex(const int a[][])        //获取hash值，将Close[t]设置为1，表示已经访问过

 {

     int t=;

     for(int i=;i<;i++)

         for(int j=;j<;j++)

             t=t*+a[i][j];

     return t;

 }

 int PrintPath(const Item p)            //递归打印路径

 {

     if(p.Pre==-)

     {

         for(int i=;i<;i++)

         {

             for(int j=;j<;j++)

                 cout<<"    "<<p.state[i][j]<<" ";

             cout<<endl;

         }

         cout<<endl;

         return ;

     }

     PrintPath(path[p.Pre]);

     cout<<p.G<<" ==>"<<endl;

     for(int i=;i<;i++)

     {

         for(int j=;j<;j++)

             cout<<"    "<<p.state[i][j]<<" ";

         cout<<endl;

     }

     cout<<endl;

     return ;

 }

 /*search()函数中的思路：

     1.将初始节点放入open。（open是优先队列，f最小的节点排在队列的最前面）

     2.从open中取出f最小的节点p,放入到path中，如果为目标节点，则递归打印路径。否则将该状态放入到close中，并生成他的扩展节点集P(就是将空白点往四个方向移动)。

     3.对于扩展出的每个子节点 temp：

         temp.calcuf()，计算f,pre,

         如果temp不在close，就把它放入open中,否则不管

     4.回到步骤2;

 八数码无解情况判断：

     初始状态和目标状态的逆序数奇偶性相同，则可到达

 */

 void Search(Item s,int end[][])

 {

     int x,y,mx,my;

     path.clear();

     Open.push(s);

     while()

     {

         Item e=Open.top();

         Open.pop();

         path.push_back(e);

         int in=GetIndex(e.state);

         Close[in]=;    //标记表示已经访问过

         int len=path.end()-path.begin()-;        //获取e节点在path中的位置，他是扩展出的节点的父节点。

         if(CalcuH(e.state,end)==)

         {

             //cout<<e.G<<endl;

             cout<<"一共需要"<<e.G<<"步"<<endl;

             PrintPath(e);

             return;

         }

         for(int i=;i<;i++)        //找到0的位置，0表示空白

             for(int j=;j<;j++)

                 if(e.state[i][j]==)

                     x=i,y=j;

         for(int i=;i<;i++)        //向四个方向扩展

         {

             mx=x+dx[i],my=y+dy[i];

             if(mx>||mx<||my<||my>)    //判断是否跑出3*3的数组

                 continue;

             swap(e.state[mx][my],e.state[x][y]);    //将空白点与周围点交换位置

             Item temp(e.state,len,e.G+,CalcuH(e.state,arraye));    //构造出新的状态节点

             swap(e.state[mx][my],e.state[x][y]);    //再交换回来

             int index=GetIndex(temp.state);        //获取hash值

             if(!Close.count(index))

             {

                 Open.push(temp);

             }

         }

     }

     return;

 }

 int main()

 {

     clock_t t=clock(),e;

     Item s(arrays,-,,CalcuH(arrays,arraye));

     if(Judge(arrays,arraye))        //判断是否有解

         Search(s,arraye);

     else

         cout<<"no path"<<endl;

     e=clock();

     cout<<"run time : "<<e-t<<" ms"<<endl;

     return ;

 }