八数码解法2
解题整体思路 ： 预处理+哈希判重+打表+输出路径
我们知道对于八数码问题而言，每一个状态就是每一个格子的编号（我们把空格看成9），那么最多有9!种，那么现在针对每一种状态都有9个数字，难道我们开一个9维数组，显然这个是非常愚蠢的做法当然计算机也是不允许开这么大的数组，那么这时候我么就不能像之前一样去判断状态重复的情况，那我们应该怎么做呢，这时候我们想到了哈希，什么是哈希大家去了解，我们可以把这些个状态压缩成一个整数，然后利用整数去映射就是说每一个整数代表一个状态，那么我么就可以开一个vis数组，利用下标就可以做到映射的效果。哈希是想到了，但是我们应该选择什么哈希函数呢，看了网上一些神牛利用的是"康托展开",也就是利用全排列都有一个对应的整数，利用哈希函数把状态压缩成整数，这样就可以做到每一个整数都是唯一对应一个状态，那么这个时候就把哈希做完了。
现在我么考虑如果是单纯的BFS+哈希，如果是多组数据是不是会超时，那么我们是不是想到由于目标状态是一定的，那么对于目标状态而言能够到达的状态是一定的是不会变得，那么这个时候我么就可以预先处理，就是先把那些目标状态能够到达的状态找出，顺便标上目标状态到该状态的路径并且标记该状态哈希值的vis数组为1，那么最后我们就可以做到不用每一次都去搜索，只要把读入的状态的哈希值找出来判断vis数组是否被标记即可，如果有输出路径，我么的路径保存在一个Path[]数组里。
其它详见代码
参考资料： 1 康托展开：X=an*(n-1)!+an-1*(n-2)!+...+ai*(i-1)!+...+a2*1!+a1*0! 其中，a为整数，并且0<=ai<i(1<=i<=n)。这就是康托展开
2 康托展开的代码
int Cantor(int s[] ， int n){
int i , j , temp , num;
num = 0;
for(i = 0 ; i < n ; i++){
temp = 0;
for(j = i+1 ; j < n ; j++){
if(s[j] < s[i]) temp++;//这里是s[j] < s[i];
}
num += factor[n-1-i]*temp;
}
return num;
}
1 uva
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 400000
struct State{
int state[9];//状态数组
int pos;//记录空格位置
string path;//记录从目标状态到当前状态的路径
};
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//方向数组
int factor[9] = {1,1,2,6,24,120,720,5040,40320};//阶乘数组
string Path[MAXN];//存储每一个到达目标状态的路径
int vis[MAXN];//判重
char dirtion[4] = {'d' , 'l' , 'u' , 'r'};//对应方向的字符，注意由于是从目标到初始必须是相反输出才能是正确的方向
queue<State>q;
//哈希函数(利用康托展开)X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!
int Hash(int s[]){
int i , j , temp , num;
num = 0;
for(i = 0 ; i < 9 ; i++){
temp = 0;
for(j = i+1 ; j < 9 ; j++){
if(s[j] < s[i]) temp++;//这里是s[j] < s[i];
}
num += factor[8-i]*temp;
}
return num;
}
//从目标状态出发预处理
void Bfs(){
while(!q.empty()) q.pop();
State goal;//目标状态
memset(vis , 0 , sizeof(vis));//初始化为每一个状态0
for(int i = 0 ; i < 8 ; i++)
goal.state[i] = i + 1;
goal.state[8] = 9;
goal.path = "" ; goal.pos = 8;
q.push(goal) ; vis[0] = 1;//目标状态标记为1
while(!q.empty()){
State cur = q.front();
q.pop();
int x , y , r , c;//表示空格的坐标
x = cur.pos/3 ; y = cur.pos%3;
for(int i = 0 ; i < 4 ; i++){//四个方向枚举
r = x + dir[i][0] ; c = y + dir[i][1];
if(r < 0 || r >= 3 || c < 0 || c >= 3) continue;
State tmp = cur;
tmp.state[tmp.pos] = tmp.state[3*r+c];//之前的空格位置换成新的编号
tmp.pos = 3*r+c;//空格的新位置
tmp.state[tmp.pos] = 9;
int hash = Hash(tmp.state);
if(vis[hash]) continue;
vis[hash] = 1;//标记为1
tmp.path += dirtion[i];//路径接着加上此时的dirtion[i]
Path[hash] = tmp.path;//这个状态的路径保存下来
q.push(tmp);
}
}
}
int main(){
//freopen("input.txt" , "r" , stdin);
Bfs();
State star ;
char c;
int t;
scanf("%d" , &t);
while(t--){
for(int i = 0 ; i < 9 ; i++){
scanf(" %c" , &c);
if(c == 'x') { star.pos = i ; star.state[i] = 9;}
else star.state[i] = c-'0';
}
getchar();
int hash = Hash(star.state);
if(vis[hash]){
for(int i = Path[hash].size()-1 ; i >= 0 ; i--)
cout<<Path[hash][i];
printf("\n");
}
if(!vis[hash]) printf("unsolvable\n");
if(t) printf("\n");
}
return 0;
}
2 杭电上面是有恶心数据“1 2 3 4 5 6 7 8 x” 应该是输出 unsolvable ZOJ上面是没有，但是我在POJ上面一直TLE，这就是我比较郁闷的地方过了三个OJ，偏偏POJ不让过
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
using namespace std;
#define MAXN 400000
struct State{
int state[9];//状态数组
int pos;//记录空格位置
string path;//记录从目标状态到当前状态的路径
};
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//方向数组
int factor[9] = {1,1,2,6,24,120,720,5040,40320};//阶乘数组
string Path[MAXN];//存储每一个到达目标状态的路径
int vis[MAXN];//判重
char dirtion[4] = {'d' , 'l' , 'u' , 'r'};//对应方向的字符
queue<State>q;
//哈希函数(利用康托展开)X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0!
int Hash(int s[]){
int i , j , temp , num;
num = 0;
for(i = 0 ; i < 9 ; i++){
temp = 0;
for(j = i+1 ; j < 9 ; j++){
if(s[j] < s[i]) temp++;//这里是s[j] < s[i];
}
num += factor[8-i]*temp;
}
return num;
}
//从目标状态出发预处理
void Bfs(){
while(!q.empty()) q.pop();
State goal;//目标状态
memset(vis , 0 , sizeof(vis));//初始化为每一个状态0
for(int i = 0 ; i < 8 ; i++)
goal.state[i] = i + 1;
goal.state[8] = 9;
goal.path = "" ; goal.pos = 8;
q.push(goal) ; vis[0] = 1;//目标状态标记为1
while(!q.empty()){
State cur = q.front();
q.pop();
int x , y , r , c;//表示空格的坐标
x = cur.pos/3 ; y = cur.pos%3;
for(int i = 0 ; i < 4 ; i++){//四个方向枚举
r = x + dir[i][0] ; c = y + dir[i][1];
if(r < 0 || r >= 3 || c < 0 || c >= 3) continue;
State tmp = cur;
tmp.state[tmp.pos] = tmp.state[3*r+c];//之前的空格位置换成新的编号
tmp.pos = 3*r+c;//空格的新位置
tmp.state[tmp.pos] = 9;
int hash = Hash(tmp.state);
if(vis[hash]) continue;
vis[hash] = 1;//标记为1
tmp.path += dirtion[i];//路径接着加上此时的dirtion[i]
Path[hash] = tmp.path;//这个状态的路径保存下来
q.push(tmp);
}
}
}
int main(){
//freopen("input.txt" , "r" , stdin);
Bfs();
State star ;
char c;
while(scanf("%c" , &c) != EOF){
if(c == 'x'){
star.pos = 0 ; star.state[0] = 9;
}
if(c != 'x') star.state[0] = c-'0';
for(int i = 1 ; i < 9 ; i++){
scanf(" %c" , &c);
if(c == 'x') star.pos = i;
star.state[i] = c-'0';
}
getchar();
int hash = Hash(star.state);
if(vis[hash]){
for(int i = Path[hash].size()-1 ; i >= 0 ; i--)
cout<<Path[hash][i];
printf("\n");
}
else printf("unsolvable\n");
}
return 0;
}