URAL_1015
立方体只有3种本质不同的旋转，因此我们可以将所有骰子的初始状态以及旋转后的衍生状态都存到一个哈希表中，每次可以用bfs或dfs模拟旋转一个骰子，同时在哈希表中查找出现了哪些其他的骰子并标记已经查找过即可。
#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXD 200010 #define HASH 100007 int ch[][6] = {{5, 3, 2, 0, 4, 1}, {0, 1, 5, 2, 3, 4}, {2, 4, 1, 3, 0, 5}}; int N, e, head[HASH], then[MAXD], st[MAXD][6], ans[MAXD], num, vis[MAXD]; int first[MAXD], E, next[MAXD]; int cmp(const void *_p, const void *_q) { int *p = (int *)_p, *q = (int *)_q; return *p < *q ? 1 : -1; } int hash(int s) { int i, h = 0; for(i = 0; i < 6; i ++) h = (h << 3) | st[s][i]; return h % HASH; } void init() { int i, j, h; memset(head, -1, sizeof(head)); for(i = 1; i <= N; i ++) { for(j = 0; j < 6; j ++) scanf("%d", &st[i][j]); h = hash(i); then[i] = head[h]; head[h] = i; } } int Insert(int s) { int i, h = hash(s); for(i = head[h]; i != -1; i = then[i]) if(memcmp(st[s], st[i], sizeof(st[i])) == 0) { if(i > N || vis[i]) return 0; vis[i] = 1; ans[num ++] = i; } then[s] = head[h]; head[h] = s; return 1; } void solve() { int i, j, k, front, cnt; cnt = 0, e = N + 1; memset(vis, 0, sizeof(vis)); memset(first, -1, sizeof(first)); for(i = 1; i <= N; i ++) if(!vis[i]) { vis[i] = 1; num = 0; memcpy(st[e], st[i], sizeof(st[i])); ans[num ++] = i; for(front = e ++; front < e; front ++) for(j = 0; j < 3; j ++) { for(k = 0; k < 6; k ++) st[e][ch[j][k]] = st[front][k]; if(Insert(e)) ++ e; } qsort(ans, num, sizeof(ans[0]), cmp); for(j = 0; j < num; j ++) next[ans[j]] = first[cnt], first[cnt] = ans[j]; ++ cnt; } printf("%d\n", cnt); for(i = 0; i < cnt; i ++) { printf("%d", j = first[i]); for(j = next[j]; j != -1; j = next[j]) printf(" %d", j); printf("\n"); } } int main() { while(scanf("%d", &N) == 1) { init(); solve(); } return 0; }