1035-cube.c

ZOJ1035Cube这题.多注意,细心就能AC(Accepted)了.

#include<stdio.h>
int mark[6],map[6],used[6],ans;
int deal(int step);
int left(int n);
int flip(int n,int s);
int getbit(int n,int i);
int main()
{
	int t,i,j,count,p;
	char string[6][50];
	scanf("%d",&t);
	for(p=1;p<=t;p++)
	{
		for(i=0;i<6;i++)
			scanf(" %s",string[i]);
		for(i=0;i<6;i++)
			map[i]=0;
		count=0;
		ans=0;
		/*将每个的信息反应到map中去*/
        for(i=0;i<6;i++)
		{
			for(j=i*7;j<i*7+6;j++)
			{
				if(string[0][j]=='X')
				{
					map[i] |=1 << (j-i*7);
					count++;
				}
				if(string[5][j]=='X')
				{
					map[i] |=1 << (15-(j-i*7));
					count++;
				}
			}
			for(j=1;j<=4;j++)
			{
				if(string[j][i*7]=='X')
				{
					map[i] |=1 << (20-j);
					count++;
				}
				if(string[j][i*7+5]=='X')
				{
					map[i] |=1 << (j+5);
					count++;
				}
			}
		}
		/*6个方块的边界上加起来必须有且只有56个1*1块*/
		if(count==56)
		{
			for(i=0;i<6;i++)
			{
				used[i]=0;
				mark[i]=0;
			}
			ans=deal(0);
		} 
		printf("Scenario #%d:\n",p);
		if(ans==1)
			printf("Yes\n");
		else
			printf("No\n");
		printf("\n");
	}
	return 0;
}
/*问题不难,主要清楚地看清边与边的啮合(关系到两条边),顶点的啮合(关系到3个点)*/
int deal(int step)
{
	int i,j,k,t1,t2,t3,t4;
	if(step==0)
	{
		mark[0]=map[0];
		used[0]=1;
		return deal(step+1);
	}
 	for(i=1;i<6;i++)
	{
		if(!used[i])
		{
			used[i]=1;
			for(j=0;j<8;j++)
			{
				mark[step]=flip(map[i],j);
			 	if(step==1)
				{
					t1=getbit(mark[1],15)&&getbit(mark[0],0);
					t2=getbit(mark[1],10)&&getbit(mark[0],5);
					/*顶点位置有重块*/
					if(t1||t2)
					  continue;
					for(k=1;k<=4;k++)
					{
						t1=getbit(mark[1],15-k);
						t2=getbit(mark[0],k);
						if(!(t1^t2))
							break;
					}
					/*边不能啮合*/
					if(k<=4)
						continue;
					if(deal(step+1))
						return 1;
					continue;
				}
				if(step==2)
				{
					t1=getbit(mark[2],15)&&getbit(mark[0],10);
					t2=getbit(mark[2],5)&&getbit(mark[1],5);
                    if(t1||t2)
						continue;
					t1=getbit(mark[2],0);
				    t2=getbit(mark[0],5)||getbit(mark[1],10);
					if(!(t1^t2))
						 continue;
					for(k=1;k<=4;k++)
					{					
						t1=getbit(mark[2],20-k)^getbit(mark[0],5+k);
						t2=getbit(mark[2],k)^getbit(mark[1],10-k);
					    if(!t1 || !t2)
						 break;
					}
					if(k<=4)
						continue;
					if(deal(step+1))
						return 1;
					continue;
				}
				if(step==3)
				{
					t1=getbit(mark[3],10)&&getbit(mark[0],15);
					t2=getbit(mark[3],0)&&getbit(mark[1],0);
					if(t1||t2)
						continue;
					t1=getbit(mark[3],5);
					t2=getbit(mark[0],0)||getbit(mark[1],15);
					if(!(t1^t2))
						continue;
					for(k=1;k<=4;k++)
					{
						t1=getbit(mark[3],k+5)^getbit(mark[0],20-k);
						t2=getbit(mark[3],k)^getbit(mark[1],20-k);
						if(!t1||!t2)
							break;
					}
					if(k<=4)
						continue;
					if(deal(step+1))
						return 1;
					continue;
				}
				if(step==4)
				{
					t1=getbit(mark[4],15)&&getbit(mark[3],15);
					t2=getbit(mark[4],10)&&getbit(mark[2],10);
					if(t1||t2)
						continue;
					t1=getbit(mark[4],0);
					t2=getbit(mark[3],10)^getbit(mark[0],15);
					if(!(t1^t2))
						continue;
					t1=getbit(mark[4],5);
					t2=getbit(mark[2],15)^getbit(mark[0],10);
					if(!(t1^t2))
						continue;
					for(k=1;k<=4;k++)
					{
						t1=getbit(mark[4],k)^getbit(mark[0],15-k);
						t2=getbit(mark[4],5+k)^getbit(mark[2],15-k);
						t3=getbit(mark[4],15+k)^getbit(mark[3],15-k);
						if(!t1||!t2||!t3)
							break;
					}
					if(k<=4)
						continue;
					if(deal(step+1))
						return 1;
					continue;
				}
				if(step==5)
				{
					t1=getbit(mark[5],0);
					t2=getbit(mark[3],15)^getbit(mark[4],15);
					if(!(t1^t2))
						continue;
					t1=getbit(mark[5],5);
					t2=getbit(mark[2],10)^getbit(mark[4],10);
					if(!(t1^t2))
						continue;
					t1=getbit(mark[5],10);
					t2=getbit(mark[1],5)^getbit(mark[2],5);
					if(!(t1^t2))
						continue;
					t1=getbit(mark[5],15);
			    	t2=getbit(mark[1],0)^getbit(mark[3],0);
					if(!(t1^t2))
						continue;
					for(k=1;k<=4;k++)
					{						
						t1=getbit(mark[5],k)^getbit(mark[4],15-k);
						t2=getbit(mark[5],k+5)^getbit(mark[2],10-k);
						t3=getbit(mark[5],k+10)^getbit(mark[1],5-k);
						t4=getbit(mark[5],k+15)^getbit(mark[3],20-k);
						if(!t1||!t2||!t3||!t4)
							break;
					}
					if(k<=4)
						continue;
					return 1;
				}

			}
			used[i]=0;
		}
	}
    return 0;
}
/*方块的几种变化*/
int flip(int n,int s)
{
	int i,j,t=n;
	if(s==0)
		return t;
	else if(s<=3)
	{
		t=left(t);
		if(s==1)
			return t;
        t=left(t);
		if(s==2)
			return t;
        t=left(t);
			return t;		
	}
	else
	{
		t=0;
		t |=getbit(n,0);
		for(i=1;i<20;i++)
			t |=(getbit(n,20-i)<<i);
		if(s==4)
			return t;
		t=left(t);
		if(s==5)
			return t;
		t=left(t);
		if(s==6)
			return t;
		return left(t);
	}
}
/*左移5位*/
int left(int n)
{
	int i=1,t;
	do
	{
		t=n & (1<<19);
		n<<=1;
		n |=(t!=0);
		i++;
	}while(i<=5);
	return n;
}
/*获得数的第i位*/
int getbit(int n,int i)
{
	return (n&(1<<i))!=0;
}