时间戳

首页 > 技术文章 > A*算法-历届试题 九宫重排

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

littlehoom 2014-03-15 16:46 原文

 历届试题 九宫重排  

时间限制：1.0s   内存限制：256.0MB
      
问题描述
　　如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

　　我们把第一个图的局面记为：12345678.
　　把第二个图的局面记为：123.46758
　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入格式
　　输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式
　　输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678.
123.46758
样例输出
3
样例输入
13524678.
46758123.
样例输出
22
 
 
fuck啊，只对了80%；骚年努力！没有过不去的坎，没有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;
}

 

 

用set来设Close表，结果可以在1s内出来，但是结果是错的，还是80%对了只。

#define _CRT_SECURE_NO_DEPRECATE
//A*八数码问题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<vector>
#include<cmath>
#include<algorithm>
#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;
set<int> cList;
set<int>::iterator iter;

bool ccmp(NODE n1,NODE n2){
    //便于二分查找
    return n1.flag<n2.flag;
}
//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);
        //CList[++clen]=n;
        cList.insert(n.flag);
        //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; }
//                    }
                    /* c1=0;c2=clen;
                    sort(CList,CList+clen+1,ccmp);
                    while(c1<c2){
                        mid=(c1+c2)/2;
                        if(CList[mid].flag>t.flag)c2=mid-1;
                        else if(CList[mid].flag<t.flag)c1=mid+1;
                        else if(CList[mid].flag==t.flag){inCL=true;break;}
                    } */
                    iter=cList.find(t.flag);
                    if(iter!=cList.end())inCL=true;
                    if (!inCL)OList.push(t);
                }
            }
        }
    }
    if (find){
        printf("%d\n", step);
    }
    else{
        printf("-1\n");
    }
    //printf("%d\n",CList.size());
}

//逆序对是否同偶或同奇
bool comp(int x, int y);

int main()
{
    char c[10];
    //while(1){
        gets(c);
        orig.init(c);
        gets(c);
        targ.init(c);
        orig.calf(targ);
        if(comp(orig.flag, targ.flag))
            AStar();
        else printf("-1\n");
    //}
    return 0;
}

inline bool comp(int x, int y){
    int t1[8],t2[8], i1=0,i2=0, m = 100000000, h;
    while(x){
        h=x/m;
        if(h>0)t1[i1++]=h;
        x%=m;
        m/=10;
    }
    m = 100000000;
    while(y){
        h=y/m;
        if(h>0)t2[i2++]=h;
        y%=m;
        m/=10;
    }
    /*for(int i=0;i<8;i++)printf("%4d",t1[i]);
    printf("\n");
    for(int i=0;i<8;i++)printf("%4d",t2[i]);
    printf("\n");*/
    m=0;h=0;
    for(int i=0;i<8;i++)for(int j=i+1;j<8;j++){
        if(t1[i]>t1[j])m++;
        if(t2[i]>t2[j])h++;
    }
    //printf("%d\n%d\n",m,h);
    if(h%2==m%2)return true;
    else return false;
}

 

推荐阅读