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
Sample Output
题目链接
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 ;
}