八数码（IDA*算法）

八数码

IDA*就是迭代加深和A*估价的结合

在迭代加深的过程中，用估计函数剪枝优化

并以比较优秀的顺序进行扩展，保证最早搜到最优解

需要空间比较小，有时跑得比A*还要快

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

int num,cnt,x,y;

int zx[]={,-,,,},zy[]={,,-,,};//1上，2左，3下，4右

int c[][];

inline void read()

{

    char cc;

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

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

      {

          cc=getchar();

          c[i][j]=cc-'';

          if(c[i][j]==){

              x=i;

              y=j;

          }

      }

}

int de[][]={{,},{,},{,},{,},{,},{,},{,},{,},{,}};　　//de[i][0/1]表示数字i在目标状态的横、纵坐标

inline int close()    //笛卡尔距离之和

{

    int mark=;

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

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

         mark+=abs(i-de[c[i][j]][])+abs(j-de[c[i][j]][]);

    return mark>>;

}

inline void dfs(int t,int pre)

{

//    cout<<t<<endl;

//    for(int i=1;i<=3;i++)

//    {

//     for(int j=1;j<=3;j++)

//      printf("%d ",c[i][j]);

//      puts("");

//    }

//    puts("");

    int clo=close();

    if(clo==){

        printf("%d\n",t);

        exit();

    }

    if(t+clo>cnt) return;

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

    if(((i+)%+)!=pre)    //若i与pre不互逆 ,便扩展

    {

        x+=zx[i];y+=zy[i];

        if(<=x&&x<=&&<=y&&y<=)

        {

            swap(c[x][y],c[x-zx[i]][y-zy[i]]);

            dfs(t+,i);

            swap(c[x][y],c[x-zx[i]][y-zy[i]]);

        }

        x-=zx[i];y-=zy[i];

    }

}

int main()

{

    read();

    for(cnt=;cnt<=;cnt++)

        dfs(,);

    return ;

}

//   加上 register 160ms
//   不加 register 108ms
//   开O2 40ms