//fn=gn+hn

 #include<iostream>

 #include<queue>

 #include<stack>

 using namespace std;

 #define num 9

 struct node

 {

     int state[];//当前状态

     struct node* parent;//父节点

     int value;//值

     int depth;//在树中的深度

     friend bool operator < (node A, node B) //按照value值小的方案构造优先级队列

     {

         return A.value > B.value;

     }

 };

 priority_queue<node> openTable;     //open表

 queue<node> closeTable;     //close表

 stack<node> Path;     //最终路径

 void init(node& s,node& g)

 {//初始化

     s.parent=NULL;

     s.depth=;

     s.value=;

     g.parent=NULL;

     g.depth=;

     g.value=;

     cout<<"please input the init status"<<endl;

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

     {

         cin>>s.state[i];

     }

     cout<<"please input the target status"<<endl;

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

     {

         cin>>g.state[i];

     }

 }

 bool isreachable(node s,node g)

 {//判断目标是否可达。若2个状态的逆序奇偶性相同则可达，不相同则不可达。

     int count1=;

     int count2=;

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

     {

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

         {

             if(s.state[i]>s.state[j]&&s.state[i]*s.state[j]!=)

             {

                 count1++;

             }

         }

     }

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

     {

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

         {

             if(g.state[i]>g.state[j]&&g.state[i]*g.state[j]!=)

             {

                 count2++;

             }

         }

     }

     if(count1%!=count2%)

     {

        return false;

     }

        return true;

 }

 int value(node a,node g)

 {//hn

     int count=;

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

     {

         if(a.state[i]==)

         {

             continue;

         }

         else if(a.state[i]!=g.state[i])

         {

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

             {

                 if(a.state[i]==g.state[j])

                 {

                     count+=abs(i/-j/)+abs(i%-j%);

                 }

             }

         }

     }

     return count+a.depth;

 }

 bool isequal(node a,node g)

 {//当前节点是否是目标

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

     {

         if(a.state[i]!=g.state[i])

         {

             return false;

         }

     }

     return true;

 }

 bool createNode(node& a,node g)

 {//产生新节点，加入open表

     bool flag=true;

     /* 计算原状态下,空格所在的行列数，从而判断空格可以往哪个方向移动 */

     int blank;//定义空格下标

     for(blank=;blank<num;blank++)

     {

         if(a.state[blank]==)

         {

             break;

         }

     }

     if(blank==num)return false;

     int x=blank/,y=blank%;//获取空格所在行列编号

     /*找到S扩展的子节点，加入open表中*/

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

     {

         int newx=x,newy=y;//新空白格坐标

         node tempnode;//临时节点，子节点

         /*移动空格*/

         switch (d)

         {

         case ://向上

             newx--;

             if(newx<)continue;

             break;

         case ://向左

             newy--;

             if(newy<)continue;

             break;

         case ://向下

             newx++;

             if(newx>)continue;

             break;

         case ://向右

             newy++;

             if(newy>)continue;

             break;

         default:

             break;

         }

         /*交换新旧空白格的内容*/

         int newblank=newx*+newy;//新空格下标

         if (newx >=  && newx <  && newy >=  && newy < )

         {

             tempnode=a;

             tempnode.state[blank]=tempnode.state[newblank];

             tempnode.state[newblank]=;

             if(a.parent!=NULL&&(*a.parent).state[newblank]==)

             {//如果新节点和爷爷节点一样，舍弃该节点

                 continue;

             }

             /*把子节点都加入open表中*/

             tempnode.parent=&a;

             tempnode.value=value(tempnode,g);

             tempnode.depth=a.depth+;

             openTable.push(tempnode);

         }

     }

     return flag;

 }

 bool findpath(node s,node g)

 {//s->g

     bool flag=true;

     /*find path*/

     openTable.push(s);

     while(true)

     {

         closeTable.push(openTable.top());

         openTable.pop();

         if(!isequal(closeTable.back(),g))

         {

             flag=createNode(closeTable.back(),g);

         }

         else

         {

             break;

         }

     }

     /*make path*/

     node tempnode;

     tempnode=closeTable.back();

     while(tempnode.parent!=NULL)

     {

         Path.push(tempnode);

         tempnode=*(tempnode.parent);

     }

     Path.push(tempnode);

     return flag;

 }

 void printpath()

 {//print path s -> g

     cout<<"move "<<Path.size()-<<" step"<<endl;

     while(Path.size()!=)

     {

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

         {

             cout<<Path.top().state[i]<<" ";

             if((i+)%==)cout<<endl;

         }

         Path.pop();

         cout<<endl;

     }

 }

 int main()

 {

     node s,g;

     init(s,g);

     if(!isreachable(s,g))

     {

         cout<<"cannot reach"<<endl;

         system("pause");

         return ;

     }

     else if (!findpath(s,g))

     {

         cout<<"findpath error"<<endl;

         system("pause");

         return ;

     }

     else

     {

         printpath();

         cout<<"done"<<endl;

     }

     system("pause");

     return ;

 }