A*算法-历届试题 九宫重排

#define _CRT_SECURE_NO_DEPRECATE
//A*八数码问题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define MAX 1
using namespace std;

int dx[4] = { 0, 0, 1, -1 }, dy[4] = { 1, -1, 0, 0 };

class NODE{
public:
    NODE(){ memset(m, 0, sizeof(m)); flag = f = g = h = 0; par = NULL; }
    ~NODE(){}
    char m[3][3];
    //矩阵对应的十进制数
    int flag;
    //估价函数
    int f, g, h;
    //空格坐标
    int tx, ty;
    //父节点
    NODE *par;
    //转换函数
    void m2f(){
        flag=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                if(m[i][j]!=‘.‘)flag = 10*flag+(m[i][j]-‘0‘);
                else { flag *= 10; tx = i; ty = j; }
            }
        }
    }
    void init(char *c){
        int i=0;
        for(int j=0;j<3;j++)for(int k=0;k<3;k++)m[j][k]=c[i++];
        m2f();
    }
    //计算f
    void calf(NODE T){
        //h是与目标位置不同数的个数
        for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)if (m[i][j] != T.m[i][j])h++;
        
        //h:离对应点的距离
        for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++){
            for (int k = 0; k < 3; k++)for (int l = 0; l < 3; l++)
                if (m[i][j] == T.m[k][l]){ h += abs(k + l - i - j); }
        }
    
        if (par != NULL){ g = par->g + 1; f = g + h; }
        else f = h;
    }
    void print(){
        printf("%d\n",flag);
    }
};

NODE orig,targ;

//Open表中按f从小到大排序
struct great{
    bool operator()(NODE N1,NODE N2){
        return N1.f > N2.f;
    }
};

//Open表和Close表
priority_queue<NODE,vector<NODE>, great> OList;
vector<NODE> CList;
vector<NODE>::iterator itor;
//A*
void AStar(){
    int step = 0;
    char temp;
    //找到结果
    bool find = false;
    OList.push(orig);
    //如果Open表空，无解
    while (!OList.empty()){
        //把Open表第一个取出，记为n，加入Close表
        NODE n = OList.top(); OList.pop();
        CList.push_back(n);
        //n是否为目标节点,是则成功退出
        if (n.h == 0){ find = true; step = n.g; break; }
        //n是否可扩展
        for (int i = 0; i < 4; i++){
            int x = n.tx + dx[i], y = n.ty + dy[i];
            if (x>-1 && x<3 && y>-1 && y < 3){
                NODE t;
                for (int i = 0; i < 3; i++)for (int j = 0; j < 3; j++)t.m[i][j] = n.m[i][j];
                t.tx = x; t.ty = y;
                temp = t.m[n.tx][n.ty];
                t.m[n.tx][n.ty] = t.m[x][y];
                t.m[x][y] = temp;
                t.m2f();
                t.par = &n;
                t.calf(targ);
                if (n.par == NULL || t.flag != n.par->flag){
                    bool inCL = false;
                    for (itor = CList.begin(); itor != CList.end(); itor++){
                        if (t.flag == itor->flag){ inCL = true; break; }
                    }
                    if (!inCL)OList.push(t);
                }
            }
        }
    }
    if (find){
        printf("%d\n", step);
    }
    else{
        printf("-1\n");
    }
}

int main()
{
    char c[10];
    //while(1){
        gets(c);
        orig.init(c);
        gets(c);
        targ.init(c);
        orig.calf(targ);

        AStar();
    //}
    return 0;
}