题目描述 Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述

在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。

输入描述 Input Description

输入初试状态，一行九个数字，空格用0表示

输出描述 Output Description

只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入 Sample Input

283104765

样例输出 Sample Output

4

数据范围及提示 Data Size & Hint

详见试题

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int c[]={,,,,,,,,};

 char mb[]={,,,,,,,,};

 int dict2[]={,,,-},

     dict1[]={-,,,};

 bool used[],sign;

 int www;

 int step[];

 char  q[][];

 int steps;

 int hash(char str[])

 {

     int i,j,k;

     int f[];

     int sum=;

     memset(f,,sizeof(f));

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

     {

         k=;

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

             if (j<str[i] && !f[j])

                 k++;

         f[str[i]]=;

         sum+=k*c[-i];

     }

     return sum;

 }

 void bfs()

 {

     int i,j,h,t;

     int x1,y1,z1,cx,cy,cz;

     memset(used,,sizeof(used));

     memset(step,,sizeof(step));

     www=hash(q[]);

     used[www]=;

     h=;

     t=;

     while (h<t)

     {

         sign=;

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

         if (q[h][i]!=mb[i])

         {

             sign=;

             break;

         }

         if (!sign)

         {

             steps=step[h];

             return;

         }

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

             if (q[h][i]==)

             {

                 x1=i/;

                 y1=i%;

                 z1=i;

                 break;

             }

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

         {

             cx=x1+dict1[i];

             cy=y1+dict2[i];

             cz=cx*+cy;

             if ((cx>=) && (cx<) && (cy>=) && (cy<))

             {

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

                     q[t][j]=q[h][j];

                 q[t][z1]=q[h][cz];

                 q[t][cz]=;

                 www=hash(q[t]);

                 if (!used[www])

                 {

                     used[www]=;

                     step[t]=step[h]+;

                     t++;

                 }

             }

         }

         h++;

     }

     steps=-;

     return;

 }

 int main()

 {

     int i;

     char in[];

     scanf("%s",in);

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

         q[][i]=in[i]-''+;

     bfs();

     printf("%d",steps);

     return ;

 }