poj 1077 八數碼

poj 1077 八數碼

這道題花了我一晚上去了看了一種解法，結果最後悲劇了，只在poj上過了，在hdu上TLE，原因是因為hdu上是多組數

據，而poj上是一組數據。。。悲劇啊，學的方法有點低效。。。

不過那個打印路徑方法倒是可以借鑒一下，從終點往起點遞歸，打印路徑。。。

貼代碼：

#include
#include
#include
#include
using namespace std;
#define N 370000
int first[9];
int last[9] = {1,2,3,4,5,6,7,8,0}; 
int f[9];
int visit[N];
int p[N][9];//保存狀態的數組 
int dist[N];//記錄路徑 
const int dx[] = {-1,0,0,1};
const int dy[] = {0,-1,1,0};
char dir[4] = {'d','r','l','u'};
void init()//好像是一個叫做康托展開的神馬東東 
{
	f[0] = 1;
	for(int i=1; i<10; i++)
		f[i] = f[i-1] * i;
} 
int hash1(int *a)//這個是求該數字0-9在全排列中的第幾個數，用來判重 
{
	int i,j;
	int s = 0;
	for(i=0; i<9; i++)
	{
		int cnt = 0;
		for(j=i+1; j<9; j++)
		{
			if(a[j] < a[i])
				cnt++;
		}
		s += f[8-i] * cnt;
	}
	return s;
}
int bfs(int fir,int las)
{
	int i,cur;
	memset(visit,0,sizeof(visit));
	memset(dist,0,sizeof(dist));
	memset(p,0,sizeof(p));
	visit[fir] = 1;
	dist[fir] = 0;
	for(i=0; i<9; i++)
	p[fir][i] = first[i];
	queueque;
	que.push(fir);
	while(!que.empty())
	{
		int temp = que.front();
		que.pop();
		if(temp == las)
			return dist[las];
		for(cur=0; cur<9; cur++)
		{
			if(p[temp][cur] == 0)
				break;
		}
		int x = cur/3;
		int y = cur%3;
		int change[9];
		for(i=0; i<4; i++)
		{
			int xx = x + dx[i];
			int yy = y + dy[i];
			if(( xx>=0 ) && ( yy>=0 ) && (xx < 3) && (yy < 3))
			{
				memcpy(change,p[temp],sizeof(change));
				change[cur] = p[temp][xx*3+yy];
				change[xx*3+yy] = 0;
				int change1 = hash1(change);
				if(visit[change1] == 0)
				{
					visit[change1] = 1;
					dist[change1] = dist[temp] + 1;
					que.push(change1);
					memcpy(p[change1],change,sizeof(change));
				}
			}
		}
	}
	return -1;
}
void print_path(int fir,int las)//從終點遞歸打印路徑 
{
	if(las == fir)
		return;
	int cur;
	int change[9];
	for(cur=0; cur<9; cur++)
	{
		if(p[las][cur] == 0)
			break;
	}
	int x = cur/3;
	int y = cur%3;
	for(int i=0; i<4; i++)
	{
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(( xx>=0 ) && ( yy>=0 ) && (xx < 3) && (yy < 3))
		{
			memcpy(change,p[las],sizeof(change));
			change[cur] = p[las][xx*3+yy];
			change[xx*3+yy] = 0;
			int change1 = hash1(change);
			if((dist[las] == dist[change1] +1) && visit[change1])
			{
				print_path(fir, change1);
				printf(%c,dir[i]);
				break;
			}
		}
	}
	return ;
}
int main()
{
	init();
	int i,k = 0; 
	char a[30];
	while(gets(a))
	{
		//getchar();
		k = 0;
		int len = strlen(a);
		for(i=0; i= '1') && (a[i] <= '8'))
				first[k++] = a[i] - '0';
			else if(a[i] == 'x')
				first[k++] = 0;
		}
		//for(i=0; i<9; i++)
		//	printf(%d ,first[i]);
		puts();
		int fir = hash1(first);//找出某一序列所對應的全排列的位次 
		int las = hash1(last);
		int ans = bfs(fir,las);
	//	printf(%d
,ans);
		if(ans < 0)
			printf(unsolvable);
		else
			print_path(fir,las);
		puts();
	}
	
	return 0;
}