poj1077_code.cpp

问题：8数码（即求解一个移动序列

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
struct node
{
	int i;
	node *next;
};
struct node2
{
	int num,just,st;
};
node2 stk[10000000];
node *head[100003];
int a[10];
int start,end;
node *tt;
bool right(int x)
{
	int i=x%99997;
	tt=head[i];
//	printf("%d x\n",x);
	while(tt!=NULL)
	{
		if(tt->i==x)return false;
		tt=tt->next;
	}
	tt=(node *)malloc(sizeof(node));
	tt->i=x;
	tt->next=head[i];
	head[i]=tt;
//	printf("%d x %d i\n",x,i);
	return true;
}
bool move(node2 in,int s,node2 &out)
{
	int t[10];
	int k,i=0,now,now2;
	int tmp=in.num;
	while(tmp!=0)
	{
		t[i]=tmp%10;
		tmp/=10;
		if(t[i]==9)now=i;
		i++;
	}
	if(s==0)
	{
		if(now<3)return false;
		now2=now-3;
	}
	else if(s==1)
	{
		if(now%3==2)return false;
		now2=now+1;
	}
	else if(s==2)
	{
		if(now>5)return false;
		now2=now+3;
	}
	else 
	{
		if(now%3==0)return false;
		now2=now-1;
	}
	k=t[now];t[now]=t[now2];t[now2]=k;
	k=1;out.num=0;
	for(i=0;i<9;i++)
	{
		out.num+=k*t[i];
		k*=10;
	}
	if(right(out.num))return true;
	return false;
}
int ans[100000];
void output(int x)
{
	int top=0;
	while(stk[x].just!=-1)
	{
		ans[top++]=stk[x].st;
		x=stk[x].just;
	}
	for(int i=top-1;i>=0;i--)
	{
		if(ans[i]==0)printf("u");
		else if(ans[i]==1)printf("r");
		else if(ans[i]==2)printf("d");
		else printf("l");
	}
	puts("");
	return ;
}
void bfs()
{
	if(start==end){puts("");return; }
	int head=0,tail=1,ttail;
	stk[0].num=start;
	stk[0].just=-1;
	right(start);
	int i,j;
	node2 tmp,out;
	while(head<tail)
	{
		ttail=tail;
		for(i=head;i<tail;i++)
		{
			tmp=stk[i];
//			printf("%d %d %d \n",i,stk[i].num,stk[i].just);
			for(j=0;j<4;j++)
			{
				if(move(tmp,j,out))
				{
//					printf("%d %d %d hes\n",tmp.num,out.num,j);
					out.st=j;
					out.just=i;
					stk[ttail++]=out;
					if(out.num==end)
					{
						output(ttail-1);
						return ;
					}
				}		//1 2 3 x 4 5 7 6 8		
			}
		}
		head=tail;
		tail=ttail;
	}
	printf("unsolvable\n");
	return ;

}
int main()
{
//	freopen("in.txt","r",stdin);
	char ch[10];
	int i,j=1;
	for(i=0;i<100000;i++)
	{
		head[i]=(node *)malloc(sizeof(node));
		head[i]=NULL;
	}
	start=0;end=0;
	for(i=0;i<9;i++)
	{
		scanf("%s",ch);
		if(ch[0]=='x')a[i]=9;
		else a[i]=ch[0]-'0';
		start+=a[i]*j;
		end+=(i+1)*j;
		j*=10;
	}
//	printf("%d %d \n",start,end);
	bfs();
	return 0;
}