2011-09-11 22:46:55Morris
d650. 好多骰子
d650. 好多骰子
作法 : 旋轉骰子後, 找一個序列最小的儲存, 之後用排序, 再檢查重覆
/**********************************************************************************/
/* Problem: d650 "好多骰子" from */
/* Language: C */
/* Result: AC(192ms, 3.8MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-11 19:50:04 */
/**********************************************************************************/
#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[1000000];
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;
A.dice[0] = 5, A.dice[1] = 2, A.dice[2] = 9;
A.dice[3] = 1, A.dice[4] = 8, A.dice[5] = 4;
Spin_dice(A, 0);
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++) {
for(j = 0; j < 6; j++)
scanf("%d", &A.dice[j]);
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;
}
內容 ：
今天可愛的小涵製作了好多骰子，每個骰子都是 正立方體，骰子的每個面上面都有一些小圓點(至少一個)，圓點的個數表示骰子該面的點數。但是她製作完成後，發現雖然有些骰子由某個角度看起來不相同，但 經過旋轉後，就是相同的骰子了。(只要骰子經過旋轉後與另一骰子的各相對位置點數相同，就視為相同的骰子，也就是說不考慮點數排列形狀的方向性。)
小涵想要知道，在她所製作的骰子中，有幾種不相同的骰子呢？
輸入說明
：
輸入資料第一行有一個正整數n，表示小涵共製作了幾個骰子。
接 著共有n行，每行表示一顆骰子的點數，依序有六個正整數a,b,c,d,e,f，表示該位置的小圓點數，如圖所示，其中，d位於圖中a所在位置的對面，e 位於圖中b所在位置的對面，f位於圖中c所在位置的對面。(n<=1000000,0<a,b,c,d,e,f<2^31)
輸出說明
：
輸出小涵共製作了幾種不相同的骰子。
範例輸入 ：
5 8 4 5 2 9 8 1 2 4 5 8 9 1 8 4 5 9 2 5 2 9 1 8 4 1 2 3 4 5 6
範例輸出 ：
4
提示
：
在範例輸入中，其中1 2 4 5 8 9與5 2 9 1 8 4為同種骰子，其餘均不同種。
出處
：
(管理：magrady)
作法 : 旋轉骰子後, 找一個序列最小的儲存, 之後用排序, 再檢查重覆
/**********************************************************************************/
/* Problem: d650 "好多骰子" from */
/* Language: C */
/* Result: AC(192ms, 3.8MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-09-11 19:50:04 */
/**********************************************************************************/
#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[1000000];
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;
A.dice[0] = 5, A.dice[1] = 2, A.dice[2] = 9;
A.dice[3] = 1, A.dice[4] = 8, A.dice[5] = 4;
Spin_dice(A, 0);
while(scanf("%d", &n) == 1) {
for(i = 0; i < n; i++) {
for(j = 0; j < 6; j++)
scanf("%d", &A.dice[j]);
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;
}
上一篇：d449. 垃圾信件