bfs.cpp

八数码

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

char pos[362881];
int step[362881];
int quene[362881];
int move[4][2] = {0,1,0,-1,1,0,-1,0};
int numtemp[8] = {40320,5040,720,120,24,6,2,1};

int getpos(int *p)
{
	int n,m,num;
	int count[9];
	for(n = 0 ; n < 9; n++) count[n] = n;
	for(n = 0 , num = 0; n < 8; n++)
	{
		num = num + (count[p[n]-1]) * numtemp[n];
		for(m = p[n]-1;m < 9;m++) count[m]--;
	}
	return num;
}

void InitBFS()
{
	int temp[9];
	int n,m,x,y;
	int i,j,k,h,f;
	int countstep,num,len,tr,p;


	k = 0;
	len = 1;
	countstep = 1;
	quene[0] = 234567891;
	
	for(;k < len; countstep++)
	{
		m = len;
		for(;k<m;k++)
		{
			num = quene[k];
			
			for(j=0 , n = 100000000;j<9;j++,n = n/10)
			{
				temp[j] = num / n;
				num = num % n;
				if(temp[j] == 1) h = j;
			}

			x = h/3;
			y = h%3;
			
			for(i=0;i<4;i++)
			{	
				if(x+move[i][0] >=0 && x+move[i][0] < 3
					&& y+move[i][1] >=0 && y+move[i][1] < 3)
				{
					temp[x*3+y] = temp[(x+move[i][0])*3 + y+move[i][1]];
					temp[(x+move[i][0])*3 + y+move[i][1]] = 1;

					
					p = getpos(temp);
				
					if(pos[p] == 0)
					{
					    for(f=0,num = 0;f<9;f++) num = num*10 +temp[f];
						pos[p] = 1;
						quene[len++] = num;
						step[p] = countstep;
					}

					temp[(x+move[i][0])*3 + y+move[i][1]] = temp[x*3+y];
					temp[x*3+y] = 1;
				}
			}
		}
	}
}

int main()
{
	int temp[9],num,times;
	num = times = 0;
	memset(pos,0,sizeof(char)*362881);
	InitBFS();
	while(scanf("%d",&temp[times++])!=EOF)
	{	
		temp[times-1]++;

		if(times == 9)
		{
			num = getpos(temp);
			if(pos[num] == 0) printf("Impossible\n");
			else printf("%d\n",step[num]);
			num = times = 0;
		}
	}
	return 0;
}