1077.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
#include"queue"
#include"stack"
#include"algorithm"
using namespace std;
//#define __int64 long long

int const prime=507071;
int m[prime];
int from[prime];
__int64 a[prime],object;

int find(__int64 s)
{
	int k=s%prime;
	
	while(m[k]&&a[k]!=s)
		k=(k+1)%prime;
	return k;
}

struct node
{
	char map[3][3];
	char x,y;
	int times;
	int id;
};

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
inline bool inmap(int x,int y)
{
	return 0<=x&&x<3&&0<=y&&y<3;
}

queue<node> q;



int search(node begin)
{
	node nd;
	int i,k,xx,yy;

	while(!q.empty())
		q.pop();
	q.push(begin);
	
	while(!q.empty())
	{
		nd=q.front();
		q.pop();

		for(i=0;i<4;i++)
		{
			if(inmap(xx=nd.x+dx[i],yy=nd.y+dy[i]))
			{
				swap(nd.map[nd.x][nd.y],nd.map[xx][yy]);
				
				k=find( *(__int64*)nd.map );
								
				if(!m[k])
				{
					m[k]=i+1;//nd.times+1;
					a[k]=*(__int64*)nd.map;
					from[k]=nd.id;

					nd.times++;
					nd.x=xx;nd.y=yy;
					nd.id=k;

					q.push(nd);
					
					nd.id=from[k];
					nd.times--;
					nd.x=xx-dx[i];nd.y=yy-dy[i];
				}
				
				if(*(__int64*)nd.map==object)
					return nd.times;
				swap(nd.map[nd.x][nd.y],nd.map[xx][yy]);

			}//if
		}//for
	}
return 0;
}		
int main()
{
	node ndb,nde;
	int i,t,j;
//	cin>>t;
//	while(t--)
	{
		memset(m,prime,0);
		for(i=0;i<3;i++)
		for(j=0;j<3;j++)
		{
			cin>>ndb.map[i][j];
		//	ndb.map[i][j]-='0';
			
			if(ndb.map[i][j]=='x')
				ndb.x=i,ndb.y=j;
			
		}
		
		for(i=0;i<3;i++)
		for(j=0;j<3;j++)
		{
			//cin>>
				nde.map[i][j]=i*3+j+1+'0';;
		//	nde.map[i][j]-='0';
		}
		nde.map[2][2]='x';

		ndb.times=1;
		object=*(__int64 *)nde.map;
		
		m[ ndb.id=find( *(__int64 *)ndb.map ) ]=-1;
		

		if(*(__int64 *)ndb.map==object)
			//cout<<0<<endl
			;
		else 
		{
			if(!search(ndb))cout<<"unsolvable"<<endl;
			else 
			{
				stack<int> st;
				i=find( object );
				while(m[i]>=0)
				{
					st.push(m[i]);
					i=from[i];
				}
				while(!st.empty())
				{
					switch(st.top()-1)
					{
					case 0:cout<<'r';break;
					case 1:cout<<'l';break;
					case 2:cout<<'d';break;
					case 3:cout<<'u';break;
					}
					st.pop();
				}
				cout<<endl;
			}
		}
	}
	return 0;
		
}