启发式的搜索策略

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#define inf 0x7fffffff   //整数的最大值
using namespace std;
struct node{
    int map[3][3],x,y,f,g,h;
    friend bool operator < (node a,node b){
        return a.f > b.f;   //从小到大自动排序
    }
}start,target;  //定义开始状态和目标状态
int step[400010],v[400010],book[400010],targetNum=46234;
char str[4]={'u','d','l','r' };
int Can[10]={1,1,2,6,24,120,720,5040,40320 };  //全排列的压缩序列
int an[4][2]={-1,0, 1,0, 0,-1, 0,1 };  //上下左右的移动
int Cantor(node cur){ //康托展开
    int an[10],k=0,sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++)
            an[k++]=cur.map[i][j];  //将二维转化为一维
    for (int i=0 ;i<9 ;i++){
        int k=0;
        for (int j=i+1 ;j<9 ;j++)
            if (an[i]>an[j]) k++;
        sum += k*Can[9-i-1];  //求出当前全排列是初始全排列的第几个
    }
    return sum+1;
}
int checkRoad(node an) {  ///判断此时奇偶性（因为每次调换都不会改变其奇偶性）
    int a[10],k=0,sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++)
            a[k++]=an.map[i][j];  //将二位状态空间转化为一维
    for (int i=0 ;i<k ;i++) 
        if (a[i]!=0)
            for (int j=0 ;j<i ;j++)
                if (a[j]>a[i]) sum ++;  //判断移动是否需要变化逆序
    if (sum&1) return 0;   //奇数返回0
    return 1;  
}
void printRoad(node cur){   //输出移动路径
    string ans;
    int sum=targetNum;
    while (step[sum] != -1){  //如果上一个状态存在
        switch (v[sum]) {  //选择从上一个状态到达此状态经过的步骤
            case 0 : ans += str[0];break;
            case 1 : ans += str[1];break;
            case 2 : ans += str[2];break;
            case 3 : ans += str[3];break;
        }
        sum=step[sum];
    }
    for (int i=ans.size()-1; i>=0; i--)  cout<<ans[i];
    cout<<endl;
    return ;
}
int getH(node cur){
    int sum=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++){
            int u = cur.map[i][j];
            int x = u>0?(u-1)/3:2, y = u>0?(u-1)%3:2;
            sum += abs(x-i)+abs(y-j);
        }
    return sum;
}
void aStar(node cur){
    priority_queue<node> Q;  //优先队列，默认从大到小
    cur.g=0; 
    cur.h=getH(cur);  //取得该状态的h值
    cur.f=cur.g + cur.h;
    Q.push(cur);  //将f作为比较关键字存入到Q中
    memset(book,-1,sizeof(book));   //初始化
    memset(step,-1,sizeof(step));
    memset(v,-1,sizeof(v));
    book[Cantor(cur)]=1;   //标记已经有过这个状态
    while (!Q.empty()){
        cur=Q.top();Q.pop();  //取出最小的路径状态
        if (Cantor(cur)==targetNum){  //如果已经到达目标
            printRoad(cur);   //打印行走的路径
            return ;
        }
        for (int i=0 ;i<4 ;i++){   //上下左右移动
            target.x=cur.x+an[i][0];
            target.y=cur.y+an[i][1];
            int x=cur.x ,y=cur.y ;
            for (int u=0 ;u<3 ;u++)  //初始化移动后的状态
                for (int v=0 ;v<3 ;v++)
                    target.map[u][v]=cur.map[u][v];
            if (target.x<0||target.x>=3||target.y<0||target.y>=3) continue;  //保证不会移出格子
            swap(target.map[target.x][target.y],target.map[x][y]);
            int sum=Cantor(target);
            if (book[sum]==-1){   //如果这个状态还不存在
                if (checkRoad(target)==0) continue;
                book[sum]=1;
                target.g=cur.g+1;  //路径都是一样的1
                target.h=getH(target);   //取得新的h值
                target.f=target.g+target.h;
                step[sum]=Cantor(cur);  //用来标记上一个的状态
                v[sum]=i;  //用来标记走的方向
                Q.push(target);   
            }
        }
    }
    return ;
}
int main(){
    char str[100];  //存储了初始字符串
    while (cin.getline(str,100)){  //读入
        int tx=0,ty=0;
        for (int i=0 ;i<strlen(str) ;i++){   //遍历读入的字符串
            if (str[i]>='0' && str[i]<='9') {
                start.map[tx][ty]=str[i]-'0';  //初始化开始状态
                if (++ty==3) {tx++;ty=0; }
            } else if (str[i]=='x') {
                start.map[tx][ty]=0;  //将x以0的形式存储
                start.x=tx ;start.y=ty ;  //记录开始的x的坐标
                if (++ty==3) {tx++;ty=0; }
            }
        }
        if (checkRoad(start)==0) {  //判断是否能够移到
            cout<<"unsolvable"<<endl;
            continue; 
        } 
        aStar(start);
    }
    return 0;
}