即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

hdu 1043 Eight 经典八数码相关疑难问题

编程语言 The_star_is_at 17℃ 0评论

hdu 1043 Eight 经典八数码问题 

题意描述:给出一个3×3的矩阵(包含1~8数字和一个字母x),经过一些移动格子上的数后得到连续的1~8,最后一格是x,要求最小移动步数。
算法分析:经典的八数码问题。八数码属于搜索方面的问题,经典解法有bfs、A*、IDA*等等。网上资料很多,这里简单介绍一下A*。
A*:f=g+h函数。g表示从起点到当前点的移动步数,h表示对当前点到目标点的最小移动步数的预测。除去起点和目标点,我们走在任意一点上的时候,下一步很容易想到应该选择f较小的继续。(对于h的计算我们可以用曼哈顿距离公式)
康托展开:这道题里面的作用在于实施hash函数,对于当前这一步后得到一个新的矩阵,用康托展开公式计算这个矩阵的hash值,用在宽搜时判断。

还有一点优化的地方:判断当前矩阵是否可以达到目标矩阵(矩阵里两个数实施交换后,逆序数的奇偶性和目标矩阵一致才可以有机会达到目标矩阵)

const int maxn=10;
const int M = 400000+10;

struct node
{
    int mase[3][3];
    int x,y;
    int f,g,h;
    int flag;
    friend bool operator < (node a,node b)
    {
        return a.f > b.f;
    }
}start,tail;
int pre[M],v[M];

char str[4]={'u','d','l','r' };
int Can[10]={1,1,2,6,24,120,720,5040,40320 };
const int destination=46234;
int Cantor(node cur) ///康托展开
{
    int an[10],k=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++)
            an[k++]=cur.mase[i][j];
    int sum=0;
    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 is_ok(node an) ///判断此时奇偶性
{
    int a[10],k=0;
    for (int i=0 ;i<3 ;i++)
        for (int j=0 ;j<3 ;j++)
            a[k++]=an.mase[i][j];
    int sum=0;
    for (int i=0 ;ia[i]) sum ++ ;
    if (sum&1) return 0;
    return 1;
}

void print(node cur)
{
    string ans;
    int sum=destination;
    while (pre[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=pre[sum];
    }
    int len=ans.size() ;
    for (int i=len-1 ;i>=0 ;i--) putchar(ans[i]);
    return ;
}

pair pii[10];
int getH(node cur)
{
    int r=0,c=0;
    for (int i=1 ;i<=9 ;i++)
    {
        pii[i%9].first=r ;
        pii[i%9].second=c;
        c++;
        if (c==3) {r++;c=0; }
    }
    int sum=0;
    for (int i=0 ;i<3 ;i++)
    {
        for (int j=0 ;j<3 ;j++)
        {
            int u=cur.mase[i][j];
            sum += abs(pii[u].first-i)+abs(pii[u].second-j);
        }
    }
    return sum;
}

int vis[M];
int an[4][2]={-1,0, 1,0, 0,-1, 0,1 };
void A_star(node cur)
{
    priority_queue Q;
    cur.g=0 ;cur.h=getH(cur);
    cur.f=cur.g + cur.h ;
    cur.flag=-1;
    Q.push(cur);
    memset(vis,-1,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    memset(v,-1,sizeof(v));
    vis[Cantor(cur) ]=1;
    while (!Q.empty())
    {
        cur=Q.top() ;Q.pop() ;
        if (Cantor(cur)==destination)
        {
//            cout<=3||tail.y<0||tail.y>=3) continue;
            swap(tail.mase[tail.x][tail.y],tail.mase[x][y]);
            int sum=Cantor(tail);
            if (vis[sum]==-1)
            {
                if (is_ok(tail)==0) continue;
                vis[sum]=1;
                tail.g=cur.g+1;
                tail.h=getH(tail);
                tail.f=tail.g+tail.h;
                if (tail.x==x+1) tail.flag=1;
                else if (tail.x==x-1) tail.flag=0;
                else if (tail.y==y-1) tail.flag=2;
                else if (tail.y==y+1) tail.flag=3;
                pre[sum]=Cantor(cur);
                v[sum]=i;
                Q.push(tail);
            }
        }
    }
    return ;
}

int main()
{
    char str[100];
    while (gets(str))
    {
        int r=0,c=0;
        int len=strlen(str);
        int ok=0;
        for (int i=0 ;i='0' && str[i]<='9')
            {
                start.mase[r][c]=str[i]-'0';
                c++;
                if (c==3) {r++;c=0; }
            }
            else if (str[i]=='x')
            {
                start.mase[r][c]=0;
                start.x=r ;start.y=c ;
                c++;
                if (c==3) {r++;c=0; }
            }
        }
        int sum=Cantor(start);
        if (sum==destination) {printf("\n");continue; }
        if (is_ok(start)==0) {printf("unsolvable\n");continue; }
        A_star(start);
        printf("\n");
    }
    return 0;
}





转载请注明:CodingBlog » hdu 1043 Eight 经典八数码相关疑难问题

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情