2014-07-21

UVa 10877 - Diceoids

1. Problem
2. Input
3. Output
4. Sample Input
5. Output for Sample Input
6. Solution

Problem

The following picture shows four dice. Or are they all dice?

Artifacts (a) and (b) are dice; (c) and (d) are not dice, but they are the same—you can see that by a suitable rotation of (d). Thus, here we have two classes of dice-like artifacts (diceoids), classified by comparison under suitable rotations.

You are given a bag of diceoids, and your job is to classify them and report how many classes there are. (Your job is not to determine how many are dice.) To facilitate description of diceoids in a text medium, we label the faces of the cube:

then a diceoid is encoded as a sequence of six numbers dA , . . . , dF , meaning that face i bears di dots. Example: 5 3 6 2 1 4 means that face A has 5 dots, face B has 3 dots, face C has 6 dots, etc. It is entirely possible that different faces have the same number of dots, e.g., 2 2 2 3 3 3, but every face has at least 1 dot and at most 6 dots.

Input

The input file contains several test cases. The description of each test case is given below:

Each test case begins with the number of diceoids n (n<=1000), followed by the description of n dicecoids.

Output

For each test case your program should output the number of classes. Follow the format specified in the output for sample input.

Sample Input

7
5 3 6 2 1 4
4 1 5 3 2 6
5 6 3 2 4 1
4 5 1 3 6 2
2 2 2 3 3 3
2 3 2 3 3 2
1 1 1 1 1 1
0

Output for Sample Input

Solution

題目描述：

骰子同構判斷，找到真正有多少不同的骰子架構。

題目解法：

對於每一個骰子，找到所有展開方式，紀錄一個最小表示法，最後排序找不同的個數即可。

#include<stdio.h>
#include<stdlib.h>
typedef struct {
    int dice[6];
}DICE;
void Right_turn(DICE *A) {
    static int t;
    t = A->dice[0], A->dice[0] = A->dice[4];
    A->dice[4] = A->dice[3], A->dice[3] = A->dice[1], A->dice[1] = t;
}
void Up_turn(DICE *A) {
    static int t;
    t = A->dice[0], A->dice[0] = A->dice[5];
    A->dice[5] = A->dice[3], A->dice[3] = A->dice[2], A->dice[2] = t;
}
void clockwise(DICE *A) {
    static int t;
    t = A->dice[2], A->dice[2] = A->dice[4];
    A->dice[4] = A->dice[5], A->dice[5] = A->dice[1], A->dice[1] = t;
}
DICE Data[2048];
int cmp(const void *a, const void *b) {
    static DICE *i, *j;
    static int k;
    i = (DICE *)a, j = (DICE *)b;
    for(k = 0; k < 6; k++)
        if(i->dice[k] != j->dice[k])
            return i->dice[k] - j->dice[k];
    return 0;
}
void Print(DICE A) {
    static int i;
    for(i = 0; i < 6; i++)
        printf("%d ", A.dice[i]);
    puts("");
}
void Spin_dice(DICE A, int store) {
    static int i, j;
    for(i = 0; i < 6; i++)
        Data[store].dice[i] = A.dice[i];
    for(i = 0; i < 4; i++) {
        for(j = 0; j < 4; j++) {
            if(cmp(&Data[store], &A) > 0)
                Data[store] = A;
            clockwise(&A);
        }        
        Right_turn(&A);
    }
    Up_turn(&A);
    for(i = 0; i < 2; i++) {
        for(j = 0; j < 4; j++) {
            if(cmp(&Data[store], &A) > 0)
                Data[store] = A;
            clockwise(&A);
        }        
        Up_turn(&A), Up_turn(&A);
    }
}
main() {
    int n, i, j;
    DICE A;// 前右上後左下
    while(scanf("%d", &n) == 1 && n) {
        for(i = 0; i < n; i++) {
        	scanf("%d %d %d %d %d %d", &A.dice[0], &A.dice[1], &A.dice[2], 
                        &A.dice[3], &A.dice[5], &A.dice[4]);
            Spin_dice(A, i);
        }
        int Ans = 1;
        qsort(Data, n, sizeof(DICE), cmp);
        for(i = 1; i < n; i++) {
            if(cmp(&Data[i], &Data[i-1]))
                Ans++;
        }
        printf("%d\n", Ans);
    }
    return 0;
}

Morris' Blog