UVa 253 立方着色

UVa 253 立方体着色

思想：判断一个立方体能否由另一个立方体旋转得到。主要有3个基本操作，沿x、y、z轴进行0、1、2、3次旋转。

（组合数学里在求等价类时就有介绍过立方体的旋转，主要分为4种，一是不旋转即恒等置换，二是以相对两面中心连线为轴的旋转，三是以相对两顶点连线为轴的旋转，四是以相对两边中心连线为轴的旋转。其实这样的旋转都可由以上3种基本操作完成。）可以枚举出所有24种变换，但容易出错，这里就直接进行相应旋转。

方法参考的训练指南P16例8，但实现有所不同。这里定义了相应的三种基本操作，即left、up、zy。思想是把每个面都先旋转到1号面，即这里的顶面，然后固定该面和其对面，进行0到3次的旋转，这样，6乘4枚举了所有24种可能。书上只定义两个基本操作，因为两个基本操作已经足够完成所有旋转。这里定义3个只是按照自己最初的理解来实现。

上述方法只是枚举了所有的变化，还需要将题目中的颜色和变换相映射。这促使了我枚举24种状态的想法。（本来只是在枚举状态的时候并进行比较的，而其实这样枚举出所有状态对于输入来说是省略了很多重复计算，效率提高很多；如果你对每个输入都进行一次枚举。。。）

所以这里我觉得一个很重要的启示就是存在重叠子问题时不要进行重复计算，要从全局多组输入数据考虑。（因为边枚举边判断的本意，是在找到匹配的之后立即停止枚举，本意是为了省略其他多余的计算，提高效率；但从全局来看，进行了多次子问题的重复计算。）

另外，输入数据最后一行先有一个换行再是EOF，所以main里的while后的那一段不需要，注释掉就AC了。可以用scanf读入就不用考虑这个了。（这里一行没有空格，所以可用scanf）

Code：

#include<stdio.h>
#include<string.h>

void rotate(int* T, int* s);
void func();
bool find(char* s1, char* s2);

int left[]={2,1,5,0,4,3};//1面倒向3面 
int up[]={4,0,2,3,5,1};//1面倒向5面 
int zy[]={0,2,4,1,3,5};//沿1、6直线进行向左旋转 

int state[24][6];

int main()
{
 char s1[7],s2[7];
 char c;
 int i=0;
 func();
 /*for(int i=0;i<24;++i)
 {
  for(int j=0;j<6;++j)
   printf("%d ",state[i][j]);      
  printf("\n");
 }*/
 while((c=getchar())!=EOF)
 {
  if(c!='\n')
  {
   if(i<6) s1[i++]=c;
   else if(i==6) { s1[i]='\0'; s2[i++%6]=c;}
   else { s2[i++%6]=c;}          
  }
  else
  {
   s2[i]='\0';
   i=0;
   if(find(s1,s2)) printf("TRUE\n");
   else printf("FALSE\n");
  }                        
 } 
 //s2[i]='\0';
 //if(find(s1,s2)) printf("TRUE\n");
 //else printf("FALSE\n"); 
 return 0;
}

bool find(char* s1, char* s2)
{
 char color[7];    
 for(int i=0;i<24;++i)
 {
  memset(color,0,sizeof(color));
  for(int j=0;j<6;++j)
  {
   color[j]=s1[state[i][j]];       
  }       
  color[6]='\0';
  if(strcmp(color,s2)==0) return true;
 }    
 return false;
}

void rotate(int* T, int* s)
{
 int temp[6];
 memcpy(temp,s,sizeof(temp));
 for(int i=0;i<6;++i)
  s[i]=T[temp[i]];    
}

void func()
{
 int k=0;
 int str[6]={0,1,2,3,4,5};
 int s[6];
 for(int i=0;i<6;++i)
 {//依次将6个面通过两个基本操作旋转至1号面，即顶面 
  memcpy(s,str,sizeof(s));
  if(i==1) { rotate(up,s);}
  else if(i==2) { rotate(left,s); rotate(left,s); rotate(left,s);}       
  else if(i==3) { rotate(left,s);}
  else if(i==4) { rotate(up,s); rotate(up,s); rotate(up,s);}
  else if(i==5) { rotate(up,s); rotate(up,s);}
  
  for(int j=0;j<4;++j)
  {
   memcpy(state[k++],s,sizeof(s));
   rotate(zy,s);       
  }
 }     
}