首页 > 技术文章 > [刷题]算法竞赛入门经典(第2版) 4-4/UVa253 - Cube painting

xienaoban 2016-08-01 15:31 原文

书上具体所有题目: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次旋转,旋转需要要不停地赋值。

推荐阅读