int n, u;  

   char path[1000]; 

   n = 1;   

   path[0] = move[0];

   u = parent[0];  

   while(parent[u] != -1)

   {      

      path[n] = move[u]; 

      ++n;    

      u = parent[u];

   }  

   for(int i=n-1; i>=0; --i)

   {       

       cout<<md[path[i]];

   }

   cout<<endl;

}

int main()

{  

   node start; 

   char ch;

   int i;

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

   {    

      cin>>ch;    

      if(ch == 'x')

         {   

         start.board[i] = 9;   

         start.space = i;   

         }    

      else      

         start.board[i] = ch - '0';  

   }   

    for (i = 0; start.board[i] == i+1 && i < 9; ++i) ;

    if (i == 9) cout<<endl;

    else

     {

              BFS(start);   

              if(visited[0] == 1)  

                   print_path(); 

               else     

                   cout<<"unsolvable"<<endl;

    }

    return 0;

}

      将上面的源程序提交给POJ系统，系统显示的评测结果是：Accept，Memory为3844K、Time为 782MS。

      （3）编程思路2。

      状态空间的表示、结点的扩展规则与编程思路1中的方法基本相同。但结点稍作修改，定义为： struct state { char a[N]; }; 不再定义空格的位置，并且程序中空格用“0”表示。对于某一当前状态cur，执行一个循环 for (i = 0; cur.a[i] && i < N; ++i) ;后，就可以确定空格位置 space=i。

      定义全局数组 state Q[MAXN+1]来作为一个队列使用，全局数组char vis[MAXN]来表示状态结点是否被访问，其中vis[i]=0，表示状态i未被访问过；vis[i]=1，表示状态i是正向扩展（从初始状态开始）来访问过的；vis[i]=2，表示状态i是反向扩展（从目标状态开始）来访问过的。全局数组foot p[MAXN]用来存储访问过的每种状态的访问足迹， 其中，p[nt].k = ct表示状态nt是由状态结点ct扩展来的，p[nt].d = i（i为0~3之一）表示状态nt是由状态结点ct按方式i扩展来的。

      用front和rear变量指示队列的队头和队尾。初始化时，初始状态start和目标状态goal均入队。

            Q[front = 1] = start;

            Q[rear = 2] = goal;

            vis[hash(start)] = 1;   // 1 代表正向

            vis[hash(goal)] = 2;   // 2 代表反向

      （4）源程序2。

#include <iostream>

using namespace std;