Cube painting UVA 253

说说:一看到给立方体染色,开始还有点小害怕。毕竟高中数学里染色问题从来都不会简单。这道题的意思就是给立方体的六个面染色,然后判断两个染了色的立方体是否一样。其实仔细一想,立方体无非三对面,若开始确定两对面。如下面图Figure 1所示:假设1,2,6,5这四个面先确定(这只有唯一一种情况)之后,再放3,4,的时候无非两种情况。但这两种情况是不一样的,这也许就是题目所说的reflection。开始的想法是找出三对面,然后比较是否相等即可,不过实在想不出怎样来排除reflection的情况。所以只能采用第二种方法。设计一个数据结构,包含一个面的对立面的编号,以及一个数组,顺序存放从该面看过去逆时针获取其余四面的编号。最后只要将立方体一固定,尝试以立方体二的各个面为底面,然后判断对立面,以及其余四面是否能通过旋转达到完全相等即可!

题目:

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.

立方体的面按照Figure 1所示编号

Figure 1.

Since a cube has 6 faces, our machine can paint a face-numbered cube in  different ways. When ignoring the face-numbers, the

因为一个立方体有6个面,我们的机器对编上号的立方体总共有种染色方案。当忽略面的编号时,

number of different paintings is much less, because a cube can be rotated. See example below. We denote a painted cube by a string of

染色的方案就少了很多,因为立方体是可以翻转的。可以看下面的例子。我们用一个6个字符的字符串表示一个染了色的

6 characters, where each character is a br, or g. The  character (  )
from the left gives the color of face i. For example,

立方体,每个字符只可能是b,r或者g.从左边开始第i个字符(1<=i<=6)表示第i面。

Figure 2 is a picture of rbgggr and Figure 3 corresponds to rggbgr. Notice that both cubes are painted in the same way: by rotating it

比如Figure 2就可以用rbgggr表示。Figure 3 和rggbgr相对应。注意两个立方体的着色方式其实是一样的:将其中一个沿轴

around the vertical axis by 90  , the one changes into the other.

水平旋转90度,就变成了另外一个。

Input

The input of your program is a textfile that ends with the standard end-of-file marker. Each line is a string of 12 characters. The first 6

输入是一个文本文件以EOF结束。每一行输入有12个字符。前6个字符代表着了色的立方体,剩下的6个字符则表示

characters of this string are the representation of a painted cube, 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

输出是一个布尔数组成的文件。输出TRUE如果第二个着色立方体可以通过旋转变为第一个,否则输出FALSE

rotation as describes above, FALSE otherwise.

Sample Input

rbgggrrggbgr
rrrbbbrrbbbr
rbgrbgrrrrrg

Sample Output

TRUE
FALSE
FALSE

源代码:

#include <stdio.h>

typedef struct describe{//当一个面为底面时
 int top;//该底面的对立面
 int around[4];//从该面看过去,其余四面按逆时针排列
}DES;

DES cube[6];
char c[13],c1[7],c2[7];

void init();//将各面信息初始化
void get_des();//从字符串分解各面的representation
int judge(int);//判断两立方体是否相同

int main(){
  int i,j,k,flag;
  init();

  //freopen("data.txt","r",stdin);
  while(~scanf("%s",c)){
    get_des(c,c1,c2);
    flag=0;
    for(i=0;i<6;i++)
        if(c2[i]==c1[0])//若立方体二有一面与立方体一的着色相同
            if(judge(i)){
                printf("TRUE\n");
                flag=1;
                break;
            }

    if(!flag) printf("FALSE\n");
  }
  return 0;
}

void get_des(){
 int i,j;
 for(i=0;i<6;i++)
    c1[i]=c[i];

 for(i=6,j=0;i<12;i++,j++)
    c2[j]=c[i];

}

void init(){//为方便起见,将题目中面的序号都减一
 cube[0].top=5;
 cube[0].around[0]=1,cube[0].around[1]=3,cube[0].around[2]=4,cube[0].around[3]=2;
 cube[5].top=0;
 cube[5].around[0]=1,cube[5].around[1]=2,cube[5].around[2]=4,cube[5].around[3]=3;
 cube[1].top=4;
 cube[1].around[0]=2,cube[1].around[1]=5,cube[1].around[2]=3,cube[1].around[3]=0;
 cube[4].top=1;
 cube[4].around[0]=2,cube[4].around[1]=0,cube[4].around[2]=3,cube[4].around[3]=5;
 cube[2].top=3;
 cube[2].around[0]=1,cube[2].around[1]=0,cube[2].around[2]=4,cube[2].around[3]=5;
 cube[3].top=2;
 cube[3].around[0]=1,cube[3].around[1]=5,cube[3].around[2]=4,cube[3].around[3]=0;
}

int judge(int face){
   int i,j,k;

   if(c1[cube[0].top]!=c2[cube[face].top])
    return 0;

   for(i=0;i<4;i++){//立方体一固定,立方体二旋转,判断是否存在匹配情况
    k=0;
    for(j=0;j<4;j++)
      if(c2[cube[face].around[(i+j)%4]]!=c1[cube[0].around[j]]){
        k=1;
        break;
      }
    if(!k) return 1;
   }

   return 0;
}

Cube painting UVA 253,布布扣,bubuko.com

时间: 08-06

Cube painting UVA 253的相关文章

uva253 Cube painting(UVA - 253)

题目大意 输入有三种颜色判断两个骰子是否相同 思路(借鉴) ①先用string输入那12个字符,然后for出两个骰子各自的字符串 ②这里用的算法是先找出第一个的三个面与第二个的六个面去比较,如果找到相同的面并且他们的对面相等那么继续寻找,直到三个面都能找到相对立的面 ③如果有一个面没有找到相等的面或者相等的对面之类的那么就break循环然后直接判断FALSE如果三个面都能满足上述条件,那么就是TRUE 代码 #include <bits/stdc++.h> using namespace st

uva 253 - Cube painting(相同骰子)

习题4-4 骰子涂色(Cube painting, UVa 253) 输入两个骰子,判断二者是否等价.每个骰子用6个字母表示,如图4-7所示. 图4-7 骰子涂色 例如rbgggr和rggbgr分别表示如图4-8所示的两个骰子.二者是等价的,因为图4-8(a) 所示的骰子沿着竖直轴旋转90°之后就可以得到图4-8(b)所示的骰子. (a) (b) 图4-8 旋转前后的两个骰子 . Sample Input rbgggrrggbgr rrrbbbrrbbbr rbgrbgrrrrrg Sample

uva 253 Cube painting

 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. Figure 1. Since a cube has 6 faces, o

UVA253 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

UVA 253 Cube painting(枚举 模拟)

题意: 按如图的顺序给定2个骰子的颜色(只有r.b.g三种颜色) 问2个骰子是否一模一样 如 可表示为"rbgggr" 和 "rggbgr", 第二个就是绕着Z轴顺时针旋转90度与第一个相同的骰子. 分析: 记录一个错误的做法:并不是只要两面两面互相映射, 如rbrggb 与 rgrgbb, 即使 rb 对应 rb.gb 对应 bg. rg对应rg, 但他们并不是一模一样的骰子.(可以借助真正的骰子旋转尝试一下,就是123456 和 153426, 想象一下2与5互

UVa 253 Cube paiting

题意:输入两个骰子,判断是否等价 因为每一个面可以作顶面,共6*4种情况,枚举就可以了 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<queue> 9 #include<

UVa 253 骰子涂色

https://vjudge.net/problem/UVA-253 题意:输入两个骰子的六面颜色,判断是否等价. 思路:我最想到的是暴力,不过一直错,也不知道哪里错了.第二种方法就是在一个骰子里出现的一对颜色在第二个骰子也有,只要三对颜色都匹配成功,那么就是等价的. 1 #include<iostream> 2 #include<string> 3 #include<cstring> 4 using namespace std; 5 6 char str[20]; 7

UVa 253

背景:一次编译通过加一次ac就是这么爽!!!!!! 思路:枚举六个面朝上,每种情况旋转4次的所有情况,一共24种,全部枚举出来比较即可!这里比较巧妙的是把每一种情况都写作一个长度为6的字符串,并在第七位加一个'\0 ',这样就可以用strcmp来比较了. #include<stdio.h> #include<string.h> int main(void){ char l[7],r[7],temp[13]; l1: while(~scanf("%s",temp)

UVA题目分类

题目 Volume 0. Getting Started 开始10055 - Hashmat the Brave Warrior 10071 - Back to High School Physics 10300 - Ecological Premium 458 - The Decoder 494 - Kindergarten Counting Game 414 - Machined Surfaces 490 - Rotating Sentences 445 - Marvelous Mazes