codevs1225 八数码难题 bfs+哈希

2018年03月19日 10点热度 0人点赞 0条评论
题目描述 Description

Yours和zero在研究A*启发式算法.拿到一道经典的A*问题,但是他们不会做,请你帮他们.
问题描述

在3×3的棋盘上,摆有八个棋子,每个棋子上标有1至8的某一数字。棋盘中留有一个空格,空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是:给出一种初始布局(初始状态)和目标布局(为了使题目简单,设目标状态为123804765),找到一种最少步骤的移动方法,实现从初始布局到目标布局的转变。

输入描述 Input Description

输入初试状态,一行九个数字,空格用0表示

输出描述 Output Description

只有一行,该行只有一个数字,表示从初始状态到目标状态需要的最少移动次数(测试数据中无特殊无法到达目标状态数据)

样例输入 Sample Input

283104765

样例输出 Sample Output

4

#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;
					strcpy(k.a,a);
					k.step=aa.step+1;
					s.push(k);
					vis[n1]=1;
				}
			}
		}
	}
	return -1;
}
int main(){
	char a[11],at[11]="123894765";
	scanf("%s",a);
	for(int i=0;i<9;i++)
		{
		if(a[i]=='0')
		a[i]=9;
		else a[i]=a[i]-'0';
		}
		a[9]=at[9]=0;
	printf("%dn",bfs(a,at));
	return 0;
}

未经允许不得转载!codevs1225 八数码难题 bfs+哈希

update

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