[刷题]算法竞赛入门经典(第2版) 4-4/UVa253 - Cube painting

书上具体所有题目:http://pan.baidu.com/s/1hssH0KO

代码:(Accepted,0 ms)

#include<iostream>
char str[15]; void change(int b) {//更换顶上的面
char t;
if(b) t = str[0], str[0] = str[1], str[1] = str[5], str[5] = str[3], str[3] = t;
else t = str[0], str[0] = str[4], str[4] = str[5], str[5] = str[2], str[2] = t;
} bool compare() {
if (str[0] != str[6] || str[5] != str[11]) return 0;
int i,j;
for (i = 0;i < 4;++i) {
for (j = 0;j < 4;++j)
if (str[(j + i) % 4 + 1] != str[j + 7]) break;
if (j == 4) return 1;
}
return 0;
} int main()
{
//freopen("in.txt", "r", stdin);
while (scanf("%s", str) != -1) {
int i;
i = str[3], str[3] = str[4], str[4] = i;
i = str[9], str[9] = str[10], str[10] = i;
for (i = 0;i < 6;++i) {
//printf("----------------%c%c%c%c%c%c\n", str[0], str[1], str[2], str[3], str[4], str[5]);
if (compare()) break;
if(i!=5) change(i%2);
}
printf((i < 6 ? "TRUE\n" : "FALSE\n"));
}
return 0;
}

分析:这题告诉我认真审题的重要性。。。题目给的各个面的输入顺序是123546,即各个对面为1-6,2-5,3-4,而我当作了123456。。。于是面与面的对应关系错了。。我说怎么老是WA。

很奇怪题目为什么要这么给各个面的顺序,按他这样做起来比较烦(至少我没发现他故意这样排能有什么快速的途径)于是我把地4和第5个数据换了个位:

i = str[3], str[3] = str[4], str[4] = i;
i = str[9], str[9] = str[10], str[10] = i;

这样绕着上下两个面的中点所形成的直线旋转比较方便(也算是历史遗留问题。。。如果一开始就没看错题目的话,应该会想别的方法,现在WA的怕了,就直接转化一下数据了事)。

题目一共有6*4=24种情况,即6个面分别朝向上方时周围4各面旋转4次,所以甚至直接枚举也是极好的。VJ看到直接列6个数组,代表各个面朝上时其他面所在的情况,代码极其简洁:

http://acm.hust.edu.cn/vjudge/problem/source/6310914。这里因为量不大,用枚举很不错啊。而我的还要做5次旋转,旋转需要要不停地赋值。

上一篇:在ORACLE存储过程中创建临时表


下一篇:codeforces 581C. Developing Skills 解题报告