1361bit.cpp

自己的ac代码 在acm.zju.edu.cn 上的题目

#include<stdio.h>
#include<queue>
using namespace std;
struct node
{
	int sn;
	int d;
};

queue< node >qu;
char u[1<<23];
int n,m,l;
int ans;
int main()
{
	int x[10],y[10];
	int dx[4]={-1,0,0,1};
	int dy[4]={0,1,-1,0};
	int x0,y0;
	int graph[25][25];
	int i,j,k;
	int sn;
	int T=0;
	while(scanf("%d%d%d",&n,&m,&l)!=EOF)
	{
		T++;
		if(n==0 && m==0)break;
		printf("Case %d: ",T);
		memset(graph,0,sizeof(graph));
		memset(u,0,sizeof(u));
		for(i=0;i<l;i++)
		{
			scanf("%d%d",&x0,&y0);
			x0--;y0--;
			x[i]=x0;
			y[i]=y0;
		}
		scanf("%d",&k);
		for(i=0;i<k;i++)
		{
			scanf("%d%d",&x0,&y0);
			x0--;y0--;
			graph[x0][y0]=1;
		}
		sn=x[0]*n+y[0];
		if(x[0]==0 && y[0]==0){ans=0;goto HOME;}
		for(i=1;i<l;i++)
		{
			x0=x[i]-x[i-1];
			y0=y[i]-y[i-1];
			for(j=0;j<4;j++)
				if(dx[j]==x0 && dy[j]==y0)break;
			sn=(sn<<2)+j;
		}
		while(!qu.empty())qu.pop();
		node te;
		te.sn=sn;
		te.d=0;
		qu.push(te);
		while(!qu.empty())
		{
			te=qu.front();qu.pop();
			sn=te.sn;
			int dep=te.d;
			int sn0;
			sn0=sn>>(2*l-2);
			x[0]=sn0/n;y[0]=sn0 % n;			
			for(i=1;i<l;i++)
			{
				
				x[i]=x[i-1]+dx[(sn>>2*(l-i-1))&3];
				y[i]=y[i-1]+dy[(sn>>2*(l-i-1))&3];
			}
			for(k=0;k<4;k++)
			{
				x0=x[0]+dx[k];y0=y[0]+dy[k];
				if(x0<0 ||x0>=n || y0<0 || y0>=m)continue;
				if(graph[x0][y0]==1)continue;
				int in=0;
				for(i=0;i<l;i++)
				{
					if(x0==x[i] && y0==y[i]){in=1;break;}
				}
				if(in==1)continue;
				if(x0==0 && y0==0){ans=dep+1;goto HOME;}
				sn0=(x0*n+y0)<<(2*l-2);
				int mask=(1<<(2*l-2))-1;
				sn0+=(sn & mask)>>2;
				sn0+=(3-k)<<(2*l-4);
				if(u[sn0]==1)continue;
				else
				{
					u[sn0]=1;
					te.d=dep+1;te.sn=sn0;qu.push(te);				
				}
			}
		}
		printf("-1\n");
		continue;				
HOME:printf("%d\n",ans);
								
	}
	return 0;
}