历届试题 九宫重排 (搜索+哈希)

2017年02月26日 10点热度 0人点赞 0条评论
问题描述
  如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。
历届试题 九宫重排  (搜索+哈希)历届试题 九宫重排  (搜索+哈希)
  我们把第一个图的局面记为:12345678.
  把第二个图的局面记为:123.46758
  显然是按从上到下,从左到右的顺序记录数字,空格记为句点。
  本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。
输入格式
  输入第一行包含九宫的初态,第二行包含九宫的终态。
输出格式
  输出最少的步数,如果不存在方案,则输出-1。
样例输入
12345678.

123.46758
样例输出
3
样例输入
13524678.

46758123.
样例输出
22

 

#include
#include
#include
#include
using namespace std;
struct node{
	int n,step;
	char a[11];
};
int ji[11]={0,1,2,6,24,120,720,5040,40320,362880},dir[4][2]={1,0,-1,0,0,1,0,-1};
int zhan(char *a){
	int n=0,k;
	for(int i=0;i<9;i++){
		k=0;
		for(int j=i+1;j<9;j++)
		if(a[i]>a[j]) k++;
		n+=k*ji[9-i-1];
	}
	return n+1;
}
int bfs(char* a,char* att){int n1=zhan(a),n2=zhan(att),x,y,x1,y1;
	bool vis[362881]={0};
	queue s;
	node aa,k;
	strcpy(aa.a,a);
	aa.step=0;
	for(int i=0;i<9;i++)
	if(a[i]==9){
		aa.n=i+1;
		break;
	}
	s.push(aa);
	vis[n1]=1;
	while(!s.empty()){
		aa=s.front();
		s.pop();
		x=aa.n/3;
		y=aa.n%3;
		if(y==0)
		y=3;
		else x++;
		for(int i=0;i<4;i++)
		{
			x1=x+dir[i][0];
			y1=y+dir[i][1];
			if(x1>0&&x1<4&&y1>0&&y1<4){
				strcpy(a,aa.a);
				swap(a[x*3+y-4],a[x1*3+y1-4]);
				n1=zhan(a);
				if(n1==n2){
					return aa.step+1;
				}
				if(!vis[n1]){
					k.n=(x1-1)*3+y1;//cout<<"K.n "<
未经允许不得转载!历届试题 九宫重排 (搜索+哈希)

update

纸上得来终觉浅, 绝知此事须躬行。