【HDU - 1043】Eight（反向bfs+康托展开）

时间：2024-09-20 22:38:14

Eight

Descriptions:

简单介绍一下八数码问题：
在一个3×3的九宫格上，填有1~8八个数字，空余一个位置，例如下图：

1 2 3
4 5 6
7 8  

在上图中，由于右下角位置是空的，你可以移动数字，比如可以将数字6下移一位：

1 2 3   1 2 3
4 5 6 → 4 5  
7 8     7 8 6

或者将数字8右移一位：

1 2 3   1 2 3
4 5 6 → 4 5 6
7 8     7   8

1~8按顺序排列的情况称为“初始状态”（如最上方图）。“八数码问题”即是求解对于任意的布局，将其移动至“初始状态”的方法。 
给定一个现有的九宫格布局，请输出将它移动至初始状态的移动方法的步骤。
Input

输入包含多组数据，处理至文件结束。每组数据占一行，包含8个数字和表示空位的‘x’，各项以空格分隔，表示给定的九宫格布局。 
例如，对于九宫格

1 2 3
  4 6
7 5 8

输入应为：1 2 3 x 4 6 7 5 8

Output

对于每组输入数据，输出一行，即移动的步骤。向上、下、左、右移动分别用字母u、d、l、r表示；如果给定的布局无法移动至“初始 状态”，请输出unsolvable。
如果有效的移动步骤有多种，输出任意即可。

Sample Input

2  3  4  1  5  x  7  6  8

Sample Output

ullddrurdllurdruldr

题目链接

https://vjudge.net/problem/HDU-1043

其实就是反向bfs，不过用了一个新的方法去存放拼图序列，康托展开即把拼图（x12345678）全排列，再用数字去表示，简而言之就是用不同的数字去代替拼图序列，使之跟简单、快速的搜索

不会康托展开不关系，点击下面链接，现学现会

https://www.cnblogs.com/sky-stars/p/11216035.html

AC代码

#include <iostream>

#include <cstdio>

#include <fstream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#define IOS ios_base::sync_with_stdio(0); cin.tie(0);

#define Mod 1000000007

#define eps 1e-6

#define ll long long

#define INF 0x3f3f3f3f

#define MEM(x,y) memset(x,y,sizeof(x))

#define Maxn 362880+5//876543210的hash值为362880 即最多出现362880种可能

using namespace std;

static const int FAC[] = {, , , , , , , , , };    // 阶乘

struct node

{

    string path;//路径

    int hashs;//hash值

    int pos;//0的位置

};

node now,net;

queue<node>q;

int dt[][]= {{,},{-,},{,},{,-}};//四个方向

char op[]="udlr";//这个与上面的搜索方向是反的，因为是反向bfs

int tmp[];//临时存储拼图的序列

int result=;//123456780    最终答案的hash值

string path[Maxn];//path[x] hash值为x的路径

int vis[Maxn];//vis[x]  hash值为x的拼图序列是否标记过

//康托展开

int cantor(int *a)

{

    int x = ;

    for (int i = ; i < ; ++i)

    {

        int smaller = ;  // 在当前位之后小于其的个数

        for (int j = i + ; j < ; ++j)

        {

            if (a[j] < a[i])

                smaller++;

        }

        x += FAC[ - i - ] * smaller; // 康托展开累加

    }

    return x+;  // 康托展开值

}

//逆康托展开

void decantor(int x, int *a)

{

    vector<int> v;  // 存放当前可选数

    for(int i=; i<; i++)

        v.push_back(i);

    for(int i=; i<; i++)

    {

        int r = x % FAC[-i-];

        int t = x / FAC[-i-];

        x = r;

        sort(v.begin(),v.end());// 从小到大排序

        a[i]=v[t];      // 剩余数里第t+1个数为当前位

        v.erase(v.begin()+t);   // 移除选做当前位的数

    }

}

void bfs()

{

    MEM(vis,);//初始化

    for(int i=; i<; i++)//tmp一开始为123456780，从这开始打散拼图

        tmp[i]=i+;

    tmp[]=;

    now.pos=;

    now.hashs=result;

    now.path="";

    path[result]="";

    vis[result]=;

    q.push(now);

    while(!q.empty())

    {

        now=q.front();

        q.pop();

        for(int i=; i<; i++)//四个方向

        {

            int tx=now.pos/+dt[i][];

            int ty=now.pos%+dt[i][];

            if(tx>=&&ty>=&&tx<=&&ty<=)//没走出去拼图

            {

                net=now;

                net.pos=tx*+ty;

                decantor(now.hashs-,tmp);//求tmp

                swap(tmp[now.pos],tmp[net.pos]);//得到新的tmp

                net.hashs=cantor(tmp);//得到新tmp对应的hash

                if(!vis[net.hashs])//这都bfs老套路了 没啥说的

                {

                    vis[net.hashs]=;

                    net.path=op[i]+net.path;

                    q.push(net);

                    path[net.hashs]=net.path;

                }

            }

        }

    }

    return;

}

int main()

{

    bfs();

    char x;

    while(cin>>x)//输入格式 没啥说的

    {

        if(x=='x')

        {

            now.pos=;

            tmp[]=;

        }

        else

        {

            tmp[]=x-'';

        }

        for(int i=; i<; i++)

        {

            cin>>x;

            if(x=='x')

            {

                now.pos=i;

                tmp[i]=;

            }

            else

            {

                tmp[i]=x-'';

            }

        }

        now.hashs=cantor(tmp);//求出tmp这个拼图序列的hash值

        if(!vis[now.hashs])//这个hash没标记过，即没产生过这个拼图序列

            cout<<"unsolvable"<<endl;

        else

            cout<<path[now.hashs]<<endl;//输出hash的路径

    }

    return ;

}

相关文章