P1379 八数码难题

 #include<iostream>

 #include<bits/stdc++.h>

 using namespace std;

 #include<vector>

 using std::vector;

 bool t[];

 int a[][];

 int ans=;

 int tx[]={,,,-,};

 int ty[]={,-,,,};

 int pc[];

 int zt=;

 int erfen(int a)

 {

     int ans=-;

     int l=,r=zt,mid=(l+r)/;

     while(l<=r)

     {

         if(pc[mid]>a)

         {

         r=mid-;

         mid=(l+r)/;

         }

         if(pc[mid]<a)

         {

             l=mid+;

             mid=(l+r)/;

         }

         if(pc[mid]==a)

         {

             ans=mid;

             return ans;

         }

      }

      return ans;

 }

 void bfs(int x,int y,int a[][],int sum)

 {

     if(erfen(a[][]*+a[][]*+a[][]*

                             +a[][]*+a[][]*+a[][]*+a[][]*+a[][]*

                             +a[][])!=-)   return ;//如果重复了，直接退出（删除节点）

     if(a[][]*+a[][]*+a[][]*

     +a[][]*+a[][]*+a[][]*+a[][]*+a[][]*

     +a[][]==)

     {

         if(sum<ans) ans=sum;

         cout<<"youyigejie"<<endl;

         return ;

     }   //判断是否目标状态

     sum++;

      pc[++zt]=a[][]*+a[][]*+a[][]*

     +a[][]*+a[][]*+a[][]*+a[][]*+a[][]*

     +a[][];

     sort(pc,pc++zt);

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

         if(tx[i]+x>=&&tx[i]+x<=&&ty[i]+y>=&&ty[i]+y<=)

             {

                 int t[][];

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

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

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

                 t[x][y]=t[tx[i]+x][ty[i]+y],t[tx[i]+x][ty[i]+y]=;

                 if(erfen(t[][]*+t[][]*+t[][]*

                             +t[][]*+t[][]*+t[][]*+t[][]*+t[][]*

                             +t[][])==-)bfs(x+tx[i],y+ty[i],t,sum);

             }

  }

 int main()

 {

     int x,y;

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

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

             {

             cin>>a[i][j];

             if(a[i][j]==) x=i,y=j;

             }

     bfs(x,y,a,);

     cout<<ans<<endl;

     return ;

 }