紫书第四章Cube painting(利用枚举法的一个题目)

浏览: 166 发布日期: 2017-12-29 分类: c

题目:Cube painting
We have a machine for painting cubes. It is supplied with three different colors: blue, red and green. Each face of the cube gets one of these colors. The cube’s faces are numbered as in Figure 1. Since a cube has 6 faces, our machine can paint a face-numbered cube in 36 = 729 different ways. When ignoring the face-numbers, the number of different paintings is much less, because a cube can be rotated. See example below. Wedenoteapaintedcubebyastringof6characters, whereeach character is a ‘b’, ‘r’, or ‘g’. The i-th character (1 ≤ i ≤ 6) from the left gives the color of face i. For example, Figure 2 is a picture of “rbgggr” and Figure 3 corresponds to “rggbgr”. Notice that both cubesarepaintedinthesameway: byrotatingitaroundthevertical axis by 90°, the one changes into the other.
Input
The input of your program is a textfile that ends with the standard end-of-file marker. Each line is a stringof12characters. Thefirst6charactersofthisstringaretherepresentationofapaintedcube, the remaining 6 characters give you the representation of another cube. Your program determines whether these two cubes are painted in the same way, that is, whether by any combination of rotations one can be turned into the other. (Reflections are not allowed.)
Output
The output is a file of boolean. For each line of input, output contains ‘TRUE’ if the second half can be obtained from the first half by rotation as describes above, ‘FALSE’ otherwise.(原题:https://cn.vjudge.net/contest...

样例:
Sample Input
rbgggrrggbgr rrrbbbrrbbbr rbgrbgrrrrrg
Sample Output
TRUE FALSE FALSE

题意:输入12个字符的字符串,前6个是一个正方体中的六个面,后6个是另一个正方体中的六个面;然后判断这两个正方体是不是同一个样的,即能否通过旋转使其这两个正方体形式完全一样;如果是相同的则输出TRUE,否则输出FALSE;

思路:将第一个正方体的6个面进行翻转,即把前6个字符的的所有对应翻转的情况全部列出来,然后让第二个正方体的六个面即后6个字符组成的字符串与这些所有情况进行比较,看能否有相同的;有相同的则就是TRUE,没有相同的则就是FALSE;(但我比较的方法是按上面下面不动,然后中间那些依次旋转);

新技巧:关于两个进行比较是否是相同的或者等价的题目中,可以把其中一个的所以情况全列出来,然后让后面这个与第一个列出来的所以情况进行比较。(这就是枚举法的一种使用方法)。(如果是输入的情况是一种情况的延伸,也可以将这种情况的所以延伸全列出来,这样输入直接比较即可);

代码:

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

    int t[6][4]={{2,3,5,4},{1,4,6,3},{1,2,6,5},{5,6,2,1},{3,6,4,1},{4,5,3,2}};
    char x[24][7];
    void sjq  (char a[])
    {
       int i,j;
       char ch;
       for(i=0;i<24;i++)
       {
           x[i][0]=a[i/4];
           x[i][5]=a[5-i/4];
           for(j=1;j<5;j++)
           {
               x[i][j]=a[t[i/4][(j+(i-1)%4)%4]-1];
            }
               x[i][6]='\0';
        }
    }
    int main()
    {
         int tag,i,y;
         char a[13],b[7],c;
         while(scanf("%s",a)!=EOF)
        {
            tag=0;
            for(i=6;i<12;i++)
                b[i-6]=a[i];
            a[6]='\0';b[6]='\0';
            sjq(a);

            c=b[3];b[3]=b[4];b[4]=c;
            for(i=0;i<24;i++)
              if(strcmp(x[i],b)==0)
            {
               tag=1;break;
            }
            if(tag)
                printf("TRUE\n");
            else
                printf("FALSE\n");
         }
         return 0;
    }
返回顶部