首页 > 代码库 > UVALIVE 3401 Colored Cubes

UVALIVE 3401 Colored Cubes

翻转立方体

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int dice24[24][10] = {{2,1,5,0,4,3}, {2,0,1,4,5,3},{2,4,0,5,1,3},{2,5,4,1,0,3},{4,2,5,0,3,1},{5,2,1,4,3,0},{1,2,0,5,3,4},{0,2,4,1,3,5},{0,1,2,3,4,5},{4,0,2,3,5,1},{5,4,2,3,1,0},{1,5,2,3,0,4},{5,1,3,2,4,0},{1,0,3,2,5,4},{0,4,3,2,1,5},{4,5,3,2,0,1},{1,3,5,0,2,4},{0,3,1,4,2,5},{4,3,0,5,2,1},{5,3,4,1,2,0},{3,4,5,0,1,2},{3,5,1,4,0,2},{3,1,0,5,4,2},{3,0,4,1,5,2}};const int MAXN = 4;int N,dice[10][6],ans;vector<string>names;int r[MAXN + 10],color[MAXN + 10][6];int id(const char * name){        string s(name);        int n = names.size();        for (int i = 0 ; i < (int) n ;i++)                if (s == names[i]) return i;        names.push_back(s);        return n;}void check(){        for (int i = 0 ; i < N; i++)                for (int j = 0 ; j < 6; j++)  color[i][dice24[r[i]][j]] = dice[i][j];        int tot = 0;        for (int j = 0 ; j < 6; j++)        {                int cnt[24];                memset(cnt,0,sizeof(cnt));                int tmp = 0;                for (int i = 0; i < N ; i++)                        tmp = max(tmp,++cnt[color[i][j]]);                tot += N - tmp;        }        ans = min(ans,tot);}void dfs(int depth){        if (depth == N)check();        else        {                for (int i = 0 ; i <24; i++)                {                        r[depth] = i;                        dfs(depth + 1);                }        }}int main(){        //freopen("sample.txt","r",stdin);        while (scanf("%d",&N) != EOF)        {                if (N == 0) break;                names.clear();                for (int i = 0 ; i < N; i++)                     for (int j = 0 ; j < 6; j++)                     {                             char tmp[30];                             scanf("%s",tmp);                             dice[i][j] = id(tmp);                     }                ans = N * 6;                r[0] = 0;                dfs(1);                printf("%d\n",ans);        }        return 0;}

 

UVALIVE 3401 Colored Cubes