【HDU - 1043】Eight（反向bfs+康托展开）
【HDU – 1043】Eight（反向bfs+康托展开）
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）全排列，再用数字去表示，简而言之就是用不同的数字去代替拼图序列，使之跟简单、快速的搜索
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[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}; // 阶乘 struct node { string path;//路径 int hashs;//hash值 int pos;//0的位置 }; node now,net; queue<node>q; int dt[][4]= {{1,0},{-1,0},{0,1},{0,-1}};//四个方向 char op[5]="udlr";//这个与上面的搜索方向是反的，因为是反向bfs int tmp[9];//临时存储拼图的序列 int result=46234;//123456780 最终答案的hash值 string path[Maxn];//path[x] hash值为x的路径 int vis[Maxn];//vis[x] hash值为x的拼图序列是否标记过 //康托展开 int cantor(int *a) { int x = 0; for (int i = 0; i < 9; ++i) { int smaller = 0; // 在当前位之后小于其的个数 for (int j = i + 1; j < 9; ++j) { if (a[j] < a[i]) smaller++; } x += FAC[9 - i - 1] * smaller; // 康托展开累加 } return x+1; // 康托展开值 } //逆康托展开 void decantor(int x, int *a) { vector<int> v; // 存放当前可选数 for(int i=0; i<9; i++) v.push_back(i); for(int i=0; i<9; i++) { int r = x % FAC[9-i-1]; int t = x / FAC[9-i-1]; x = r; sort(v.begin(),v.end());// 从小到大排序 a[i]=v[t]; // 剩余数里第t+1个数为当前位 v.erase(v.begin()+t); // 移除选做当前位的数 } } void bfs() { MEM(vis,0);//初始化 for(int i=0; i<8; i++)//tmp一开始为123456780，从这开始打散拼图 tmp[i]=i+1; tmp[8]=0; now.pos=8; now.hashs=result; now.path=""; path[result]=""; vis[result]=1; q.push(now); while(!q.empty()) { now=q.front(); q.pop(); for(int i=0; i<4; i++)//四个方向 { int tx=now.pos/3+dt[i][0]; int ty=now.pos%3+dt[i][1]; if(tx>=0&&ty>=0&&tx<=2&&ty<=2)//没走出去拼图 { net=now; net.pos=tx*3+ty; decantor(now.hashs-1,tmp);//求tmp swap(tmp[now.pos],tmp[net.pos]);//得到新的tmp net.hashs=cantor(tmp);//得到新tmp对应的hash if(!vis[net.hashs])//这都bfs老套路了 没啥说的 { vis[net.hashs]=1; 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=0; tmp[0]=0; } else { tmp[0]=x-'0'; } for(int i=1; i<9; i++) { cin>>x; if(x=='x') { now.pos=i; tmp[i]=0; } else { tmp[i]=x-'0'; } } now.hashs=cantor(tmp);//求出tmp这个拼图序列的hash值 if(!vis[now.hashs])//这个hash没标记过，即没产生过这个拼图序列 cout<<"unsolvable"<<endl; else cout<<path[now.hashs]<<endl;//输出hash的路径 } return 0; }
版权声明：本文为sky-stars原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。