洛谷P1379 八数码难题 (A* + 康托展开)
? 解题记录 ? ? 洛谷 ? ? 搜索 ? ? A* ? ? 补档计划第一期 ?    2017-10-01 14:39:47    570    0    0

题目描述

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

输入输出格式

输入格式:

 

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
283104765
输出样例#1:
4​​

 

A*的八数码(常数巨大的A*也算A*嘛),速度还是很可观的。关于A*解决八数码以及估价函数的问题可以参考这一篇博客:我是“这篇博客”

#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<algorithm>
#include<map>
#include<string>
using namespace std;
int des[10]={1,2,3,8,0,4,7,6,5,0};
int dpos[10]={4,0,1,2,5,8,7,6,3,0};
bool vis[1000000];
int fact[]={1,1,2,6,24,120,720,5040,40320,362880};//½×³Ë±í 

int ch(int * c){
    int n=0;
    int len=9;
    for(int i=0;i<len;i++){
        int cnt = 0;
        for(int j=i+1;j<len;j++) if(c[i]>c[j]) cnt++;
        n+=    fact[len-1-i] * cnt;
    }
    return n;
}

struct node
{
    int state[10];
    int h()
    {
        int ret=0;
        for(int i=0;i<9;i++){
                int sx=i%3,sy=i/3;
                int dx=dpos[state[i]]%3,dy=dpos[state[i]]/3;
                ret+=abs(dx-sx)+abs(dy-sy);
            }
        return ret;
    }
    int f;
    int step;
    node(int rs[],int rstep)
    {
        for(int i=0;i<9;i++){
            state[i]=rs[i]; }
        step=rstep;
    }
    node(){ }
    void judge()
    {
        f=step+h();
    }
    bool operator <(const node &a) const
    {
        return f>a.f;//¹ÀֵԽС Ô½ÓÅÏÈ 
    }
};
priority_queue<node > qn;

int fdz(int * state)
{
    for(int i=0;i<9;i++)
        if(state[i]==0)
            return i;
}

bool tryleft(int * state,int pos)
{
    if(pos%3==0) return false;
    swap(state[pos],state[pos-1]);
    return true;
}

bool tryright(int * state,int pos)
{
    if(pos%3==2) return false;
    swap(state[pos],state[pos+1]);
    return true;
}

bool tryup(int * state,int pos)
{
    if(pos/3==0) return false;
    swap(state[pos],state[pos-3]);
    return true;
}

bool trydown(int * state,int pos)
{
    if(pos/3==2) return false;
    swap(state[pos],state[pos+3]);
    return true;
}

bool cmp(int * a,int * b){
    for(int i=0;i<9;i++)
        if(a[i]!=b[i])    return 0;
    return 1;
}

int Astar()
{
    while(!qn.empty())
    {
        node org;
        node nstate=qn.top();
        int step=nstate.step;
        if(cmp(nstate.state,des))
            return step;
        int pos=fdz(nstate.state);
        qn.pop();
        org=nstate;
        if(tryleft(org.state,pos))
            if(!vis[ch(org.state)])
            {                    
                node newn(org.state,step+1);
                newn.judge();
                vis[ch(org.state)]=1;
                qn.push(newn);
            }
        org=nstate;
        if(tryright(org.state,pos))
            if(!vis[ch(org.state)])
            {
                node newn(org.state,step+1);
                newn.judge();
                vis[ch(org.state)]=1;
                qn.push(newn);
            }
        org=nstate;
        if(tryup(org.state,pos))
            if(!vis[ch(org.state)])
            {
                node newn(org.state,step+1);
                newn.judge();
                vis[ch(org.state)]=1;
                qn.push(newn);
            }
        org=nstate;
        if(trydown(org.state,pos))
            if(!vis[ch(org.state)])
            {
                node newn(org.state,step+1);
                newn.judge();
                vis[ch(org.state)]=1;
                qn.push(newn);
            }
    }
    return -1;
}

int main()
{
    int start[9];
    char s[10];
    gets(s);
    for(int i=0;i<9;i++)
        start[i]=s[i]-'0';
    node st(start,0);
    vis[ch(start)]=1;
    st.judge();
    qn.push(st);
    int ans=Astar();
    if(ans!=-1) printf("%d",ans);
    else printf("No");
    return 0;
}



上一篇: 洛谷P1177 【模板】快速排序

下一篇: POJ2777 Count Color

570 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航