本文主要是介绍hdu1043（八数码问题，广搜 + hash（实现状态压缩） ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。
#include<iostream>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>#define eps 1e-9
#define N 400000
#define P system("pause")
using namespace std;
struct node
{int map[9];int zero;int hash_id;
};
int fac[]={1,1,2,6,24,120,720,5040,40320};
int d[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //因为是逆序查找，所以上下左右，变成了
char dir[]={'d','u','r','l'}; //下上右左
int hash[N];
string path[N];
int cantor(int *s) //康拓扩展求hash值
{int count,i,j;int sum=0;for(i=0;i<8;i++){count=0;for(j=i+1;j<9;j++)if(s[i]>s[j]) count++;sum+=(fac[8-i]*count); }return sum;
}void bfs()
{ //从目标开始逆向搜索，枚举每种可能出现的排列int i;node u,v;u.zero=8;u.map[8]=0;for(i=0;i<8;i++)u.map[i]=i+1;u.hash_id=cantor(u.map); hash[u.hash_id]=1;path[u.hash_id]="";queue<node> q;q.push(u);while(!q.empty()){u=q.front();q.pop();int x=u.zero/3; //找到0的位置 int y=u.zero%3;for(i=0;i<4;i++){int nx=x+d[i][0];int ny=y+d[i][1];if(nx>=0 && nx<3 && ny>=0 && ny<3){int k=nx*3+ny; //一维数组下标 v=u;v.zero=k;v.map[u.zero]=u.map[k];v.map[k]=0;v.hash_id=cantor(v.map);}if(!hash[v.hash_id]){hash[v.hash_id]=1;path[v.hash_id]=path[u.hash_id];path[v.hash_id]+=dir[i]; q.push(v); }} }}int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);ccmemset(hash,0,sizeof(hash));bfs();char c;int s[9];while(cin>>c){if(c=='x') s[0]=0;else s[0]=c-'0';for(int i=1;i<9;i++) {cin>>c;if(c=='x') s[i]=0;else s[i]=c-'0'; }int k=cantor(s);if(!hash[k]) printf("unsolvable\n");else{string ss=path[k];reverse(ss.begin(),ss.end()); cout<<ss<<endl; }} //P; return 0;
}
这篇关于hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
