wikioi1225 八數位難題

題目描述 Description

Yours和zero在研究A*啟發式算法.拿到一道經典的A*問題,但是他們不會做,請你幫他們.

問題描述

在3×3的棋盤上，擺有八個棋子，每個棋子上标有1至8的某一數字。棋盤中留有一個空格，空格用0來表示。空格周圍的棋子可以移到空格中。要求解的問題是：給出一種初始布局（初始狀态）和目标布局（為了使題目簡單,設目标狀态為123804765），找到一種最少步驟的移動方法，實作從初始布局到目标布局的轉變。

輸入描述 Input Description

輸入初試狀态，一行九個數字，空格用0表示

輸出描述 Output Description

隻有一行，該行隻有一個數字，表示從初始狀态到目标狀态需要的最少移動次數(測試資料中無特殊無法到達目标狀态資料)

樣例輸入 Sample Input

283104765

樣例輸出 Sample Output

4

初始狀态經過一步生成新的狀态，這些狀态又經過一步生成新的狀态，就這樣生成下去，總會找到目标狀态，而且是最少次數的，因為我們每一次都會把X步能走的的找完，沒有就檢視X+1步的。這就是BFS。

當一個狀态1生成狀态2之後，狀态2又可能生成狀态1，狀态1又生成狀态2，産生了死循環，是以需要判重，我用了康托展開。

#include <stdio.h>
#include <string.h>

const int B[4]={-3,-1,1,3};

struct node
{
	int s_t[10];		//目前狀态
    long ans;			//目前步數
}d[555555];				//隊列
 
char s[10];
bool Hash[400000]={0};	//Hash
int e_t[10]={0,1,2,3,8,0,4,7,6,5},tmp[10]; //目标狀态，臨時變量
 
long Jst(int n) 		//求階乘
{
	if(n==0)	return 0;
	long jst=1;
	for(int i=1;i<=n;i++)
  		jst*=i;
 	return jst;
}

long Kto(int s[])		//康拓展開
{
	long hs=0;int co=0;
 	bool h[9]={0};
 	for(int i=1;i<=8;i++)
 	{
  		co=0;
  		for(int k=s[i]-1;k>=0;k--)
   			if(!h[k])	co++; //它前面的有幾個比它小？
  		h[s[i]]=1;
  		hs+=(co*Jst(9-i));
 	}
 	return hs+1; 		//康拓展開的規則，最後一定要加1
}
 
bool Flag(int a,int b)
{
	if((a==1 && b==-1) || (a==1 && b==-3))	return 0;
 	if((a==2 && b==-3))	return 0;
 	if((a==3 && b==1) || (a==3 && b==-3))	return 0;
 	if((a==4 && b==-1))	return 0;
 	if((a==6 && b==1))	return 0;
 	if((a==7 && b==3) ||(a==7 && b==-1))	return 0;
 	if((a==8 && b==3))	return 0;
 	if((a==9 && b==1) || (a==9 && b==3))	return 0;
 	return 1;
}

int main()
{
	int count=0;
 	scanf("%s",s);
 	for(int i=0;i<9;i++)
 	{
	 	d[1].s_t[i+1]=s[i]-'0';
  		tmp[i+1]=s[i]-'0';
 	}
 	d[1].ans=0; 
 	Hash[Kto(tmp)]=1;
 	long head=1,tail=1; 		//隊列初始化
 	int b;bool flag;
 	while(head<=tail)
 	{
  		for(int i=1;i<=9;i++)	tmp[i]=d[head].s_t[i];//取隊首
  		for(int i=0;i<=3;i++)
  		{
   			for(int j=1;j<=9;j++)
    			if(tmp[j]==0)
				{
					b=j;
					break;
				}				//找0的位置
   			if(!Flag(b,B[i]))	continue; 	//是否越界
   			int t=tmp[b];tmp[b]=tmp[b+B[i]];tmp[b+B[i]]=t; //移動
   			flag=0;
   			for(int j=1;j<=9;j++) 
			   	if(tmp[j]!=e_t[j]) 
				{
					flag=1;
					break;
				} 				//判斷是否到達目标狀态
   			if(!flag)	break;
   			long hs=Kto(tmp);
   			if(Hash[hs]==0) 	//判重
   			{
    			Hash[hs]=1;
    			tail++;
    			for(int j=1;j<=9;j++)
     				d[tail].s_t[j]=tmp[j]; //入隊
    			d[tail].ans=d[head].ans+1; //是誰生成了它，便在它的步數上加1作為自己的步數
   			}
   			t=tmp[b];tmp[b]=tmp[b+B[i]];tmp[b+B[i]]=t; //換回來供他人使用
  		}
  		head++;
  		if(!flag)	break;
 	}
 	printf("%ld\n",d[head].ans+1);
 	return 0;
}