历届试题九宫重排（bfs+康托展开（哈希））

本文主要是介绍历届试题九宫重排（bfs+康托展开（哈希）），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

　　如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。

　　我们把第一个图的局面记为：12345678.
　　把第二个图的局面记为：123.46758
　　显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
　　本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。

输入格式

　　输入第一行包含九宫的初态，第二行包含九宫的终态。

输出格式

　　输出最少的步数，如果不存在方案，则输出-1。

样例输入

样例输出

3
22

解题思路

搜索的过程容易想，主要在于已经经过的状态的标记， $map <string,int >$ 会超时，上一年这样超时，今年还是这样，感觉一年什么都没做￣へ￣
第一种方法是将string改成int做key，即将经过的状态装换成整数来标记；
第二种方法是使用康托展开，也就是相当于一种哈希的方法了，这样开一个大概4100000的数组就可以标记了,效率也更快一些.

代码实现

$map<int,int>$

#include<iostream>
#include<cstring>
#include<map>
#include<cstdio>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 19;
map<int, int> vis;
char str[maxn],str0[maxn],str1[maxn];
struct node{char str[maxn];int pos;int step;
}temp,ne;
int ans=INF;
int tranverse(char s[])
{int res=0;for(int i=0;i<10;i++){res=(res*10+(s[i]-'0'));}return res;
}
void BFS()
{queue<node>qu;int inter=tranverse(str0);vis[inter]=1;int mark=-1;for(int i=0;i<maxn;i++) {if(str0[i]=='.'){mark=i;break;}}strcpy(temp.str,str0);temp.step=0,temp.pos=mark;qu.push(temp);while(!qu.empty()){temp=qu.front();qu.pop();int p=temp.pos;if(strcmp(temp.str,str1)==0){ans=min(ans,temp.step);continue;}if(temp.step>=ans){continue;}if(p%3!=0){   //i-1strcpy(str,temp.str);str[p]=str[p-1];str[p-1]='.';int inter=tranverse(str);if(!vis[inter]){vis[inter]=1;strcpy(ne.str,str);ne.step=temp.step+1,ne.pos=p-1;qu.push(ne);}}if(p%3!=2){   //i+1strcpy(str,temp.str);str[p]=str[p+1];str[p+1]='.';int inter=tranverse(str);if(!vis[inter]){vis[inter]=1;strcpy(ne.str,str);ne.step=temp.step+1,ne.pos=p+1;qu.push(ne);}}if(p/3!=2){    //i+3strcpy(str,temp.str);str[p]=str[p+3];str[p+3]='.';int inter=tranverse(str);if(!vis[inter]){vis[inter]=1;strcpy(ne.str,str);ne.step=temp.step+1,ne.pos=p+3;qu.push(ne);}}if(p>=3){    //i-3strcpy(str,temp.str);str[p]=str[p-3];str[p-3]='.';int inter=tranverse(str);if(!vis[inter]){vis[inter]=1;strcpy(ne.str,str);ne.step=temp.step+1,ne.pos=p-3;qu.push(ne);}}}
}int main()
{cin>>str0>>str1;BFS();if(ans==INF){printf("-1\n");}else{printf("%d\n",ans);}return 0;
}

康托展开

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 4200000;
const int maxx =10;
int fac[maxx],ans=INF; 
char str[maxx],str0[maxx],str1[maxx];
bool vis[maxn];
struct node{char str[maxx];int step;int pos;
}temp,ne;
void init()
{fac[0]=1;for(int i=1;i<maxx;i++){fac[i]=fac[i-1]*i;}
}
int gethash(char str[])
{int res=0;for(int i=0;i<maxx;i++){int countt=0;for(int j=i+1;j<maxx;j++){if(str[i]>str[j]){countt++;}}res+=countt*fac[8-i];}return res;
}
void BFS()
{queue<node>qu;vis[gethash(str0)]=1;int mark=-1;for(int i=0;i<maxx;i++) {if(str0[i]=='.'){mark=i; str0[i]='0';}if(str1[i]=='.')  str1[i]='0';} strcpy(temp.str,str0);temp.step=0,temp.pos=mark;qu.push(temp);while(!qu.empty()){temp=qu.front();qu.pop();int p=temp.pos;if(strcmp(temp.str,str1)==0){ans=min(ans,temp.step);continue;}if(temp.step>=ans){continue;}if(p%3!=0){   //i-1strcpy(str,temp.str);str[p]=str[p-1];str[p-1]='0';int inter=gethash(str);if(!vis[inter]){vis[inter]=1;strcpy(ne.str,str);ne.step=temp.step+1,ne.pos=p-1;qu.push(ne);}}if(p%3!=2){   //i+1strcpy(str,temp.str);str[p]=str[p+1];str[p+1]='0';int inter=gethash(str);if(!vis[inter]){vis[inter]=1;strcpy(ne.str,str);ne.step=temp.step+1,ne.pos=p+1;qu.push(ne);}}if(p/3!=2){    //i+3strcpy(str,temp.str);str[p]=str[p+3];str[p+3]='0';int inter=gethash(str);if(!vis[inter]){vis[inter]=1;strcpy(ne.str,str);ne.step=temp.step+1,ne.pos=p+3;qu.push(ne);}}if(p>=3){    //i-3strcpy(str,temp.str);str[p]=str[p-3];str[p-3]='0';int inter=gethash(str);if(!vis[inter]){vis[inter]=1;strcpy(ne.str,str);ne.step=temp.step+1,ne.pos=p-3;qu.push(ne);}}}
}
int main()
{init();scanf("%s %s",str0,str1);BFS();printf("%d\n",ans);return 0;
}