a.cpp

ACM World Final 2008题目程序代码

#include <cstdio>
#include <cstring>
using namespace std;

int elb;
bool used[22][22][22];

struct sec
{
	int d,x[3];
	void read(char posi)
	{
		char rd1,rd2;
		scanf("%d %d %d %c%c",&x[0],&x[1],&x[2],&rd1,&rd2);
		d=rd2-'x';
		if(rd1==posi)++x[d];
	}
	bool operator==(const sec& x0) const
	{
		return d==x0.d && x[0]==x0.x[0] && x[1]==x0.x[1] && x[2]==x0.x[2];
	}
	bool visit()
	{
		bool &p=used[x[0]][x[1]][x[2]];
		if(p)return false;
		return p=true;
	}
	void unvisit()
	{
		used[x[0]][x[1]][x[2]]=false;
	}
} max,s,t;

void search(int uno)
{
	if(s==t && uno<elb)elb=uno;
	if(uno+1>=elb)return;
	for(int i1=0,dold=s.d;i1<2;++i1)
	{
	 s.x[s.d]+=i1?0:-1;
	 if(s.visit())
	 {
	  s.x[s.d]+=i1?+1:-1;
	  if(s.visit())
	  {
	   for(s.d=0;s.d<3;++s.d)if(s.d!=dold)
	    for(int i2=0;i2<2;++i2)
	    {
	     s.x[s.d]+=i2?+1:-1;
	     if(s.visit())
	     {
	      s.x[s.d]+=i2?+1:-1;
	      if(s.visit())
	      {
	       s.x[s.d]+=i2?1:0;
	       search(uno+1);
	       s.x[s.d]-=i2?1:0;
	       s.unvisit();
	      }
	      s.x[s.d]-=i2?+1:-1;
	      s.unvisit();
	     }
	     s.x[s.d]-=i2?+1:-1;
	    }
	   s.d=dold;
	   s.unvisit();
	  }
	  s.x[s.d]-=i1?+1:-1;
	  s.unvisit();
	 }
	 s.x[s.d]-=i1?0:-1;
	}
	for(int i1=0,dold=s.d;i1<2;++i1)
	{
	 s.x[s.d]+=i1?0:-1;
	 if(s.visit())
	 {
	  s.x[s.d]+=i1?+1:-1;
	  if(s.visit())
	  {
	   s.x[s.d]+=i1?+1:-1;
	   if(s.visit())
	   {
	    for(s.d=0;s.d<3;++s.d)if(s.d!=dold)
	     for(int i2=0;i2<2;++i2)
	     {
	      s.x[s.d]+=i2?+1:-1;
	      if(s.visit())
	      {
	       s.x[s.d]+=i2?1:0;
	       search(uno+1);
	       s.x[s.d]-=i2?1:0;
	       s.unvisit();
	      }
	      s.x[s.d]-=i2?+1:-1;
	     }
	    s.d=dold;
	    s.unvisit();
	   }
	   s.x[s.d]-=i1?+1:-1;
	   s.unvisit();
	  }
	  s.x[s.d]-=i1?+1:-1;
	  s.unvisit();
	 }
	 s.x[s.d]-=i1?0:-1;
	}
}

int main()
{
	for(int i=1;scanf("%d",&max.x[0]),max.x[0];++i)
	{
		scanf("%d %d",&max.x[1],&max.x[2]);
		memset(used,true,sizeof(used));
		for(int i1=1;i1<=max.x[0];++i1)
		 for(int i2=1;i2<=max.x[1];++i2)
		  for(int i3=1;i3<=max.x[2];++i3)
			used[i1][i2][i3]=false;
		s.read('-');
		t.read('+');
		elb=7;
		search(0);
		printf("Case %d: ",i);
		if(elb==7)printf("Impossible\n");
		else printf("%d\n",elb);
	}
	return 0;
}