hdu-1043（八数码+bfs打表+康托展开）

参考文章：https://www.cnblogs.com/Inkblots/p/4846948.html

康托展开：https://blog.csdn.net/wbin233/article/details/72998375

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043

题意：给出一串数（有9个，其中有一个x），表示这些数再3*3的矩阵中的排序序列，如果可以通过交换x与其他数字的操作，

最终得到目的矩阵（eg：12345678x），就输出x的移动方向。分别用u表示向上，d表示向下，l向左，r向右。

思路：考察八数码的知识，由于数据总量可以接受，可以用bfs打表的方式先列出存在的每个情况，利用康托展开的映射关系（也就是每一个序列对应一个hash值）

来求出移动的方向。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

#define MAX 400000
#define AIM 46234 //124567890对应的hash值 

bool v[MAX];
char path[MAX][40]; //总路径 
int len;

char dir[10]="durl"; //反向搜索 
int mov[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; 

//八数码状态结构体 
struct Node{
    int s[9];
    int loc;
    int status; //hash值排列值 
    int fa; //记录父状态 
    char d; //移动方向 
};
Node n[MAX];

int fac[10]={1,1,2,6,24,120,720,5040,40320,362880};  //康托展开对应的hash值 

int Inverse_cantor(int s[9])
{
    int sum=0;
    for(int i=0;i<9;i++)
    {
        int num=0;
        for(int j=i+1;j<9;j++) //逆序数计数器 （康托展开需要） 
        {
            if(s[j]<s[i]) num++;
        }
        sum+=num*fac[9-i-1];
    }
    return sum+1;
}

void count_path(Node end) //反向记录路径 
{
    int status = end.status;
    int f=end.fa;
    len=0;
    path[status][len++]=end.d;
    while(f)
    {
        path[status][len++]=n[f].d; //记录方向 
        f=n[f].fa; //查找父状态方向 
    }
}

void BFS()
{
    memset(v,0,sizeof(v));
    Node next;
    int head=0,tail=0;
    for(int i=0;i<8;i++) //目标状态 
    n[0].s[i]=i+1;
    
    n[0].s[8]=0;
    n[0].loc=8;//空位是8 
    n[0].status=AIM;
    v[AIM]=true;
    while(head<=tail)
    {
        int x=n[head].loc/3;
        int y=n[head].loc%3;
        for(int i=0;i<4;i++) //遍历四个方向 
        {
            int tx=x+mov[i][0];
            int ty=y+mov[i][1];
            if(tx<0||tx>2||ty<0||ty>2) continue;
            
            next=n[head]; //更新状态 
            next.loc=tx*3+ty; //计算新空位 
            next.s[n[head].loc]=next.s[next.loc]; //原空位替换 
            next.s[next.loc]=0; //新空位 
            next.fa=head;
            next.d=dir[i];
            next.status=Inverse_cantor(next.s);
            //判断重复，并且新入队列 
            if(!v[next.status])
            {
                v[next.status]=true;
                count_path(next);
                n[++tail]=next;
            }
        }
        head++;
    }
}

int main(void)
{
    BFS();
    char ch[3];
    Node cur;
    while(~scanf("%s",ch))
    {
        if(!strcmp(ch,"x")) cur.s[0]=0,cur.loc=0;
        else cur.s[0]=ch[0]-'0';
        for(int i=1;i<9;i++)
        {
            scanf("%s",ch);
            if(!strcmp(ch,"x"))
            cur.s[i]=0,cur.loc=i;
            else cur.s[i]=ch[0]-'0';
        }
        cur.status=Inverse_cantor(cur.s);
        if(v[cur.status])
        printf("%s
",path[cur.status]);
        else printf("unsolvable
");
    }
    return 0;
}