Colored Cubes

[問題] ACM/ICPC Asia Regional 2005 Tokyo: Problem C

[解説]

総当り。
詳細は後日付け足したいと思います。

[サンプルプログラム]

001 #include<iostream>
002 #include<string>
003 #include<map>
004 using namespace std;
005 
006 int RT[24][6] = {
007     {0, 1, 2, 3, 4, 5},
008     {0, 2, 4, 1, 3, 5},
009     {0, 4, 3, 2, 1, 5},
010     {0, 3, 1, 4, 2, 5},
011     {3, 1, 0, 5, 4, 2},
012     {3, 0, 4, 1, 5, 2},
013     {3, 4, 5, 0, 1, 2},
014     {3, 5, 1, 4, 0, 2},
015     {5, 1, 3, 2, 4, 0},
016     {5, 3, 4, 1, 2, 0},
017     {5, 4, 2, 3, 1, 0},
018     {5, 2, 1, 4, 3, 0},
019     {2, 1, 5, 0, 4, 3},
020     {2, 5, 4, 1, 0, 3},
021     {2, 4, 0, 5, 1, 3},
022     {2, 0, 1, 4, 5, 3},
023     {4, 0, 2, 3, 5, 1},
024     {4, 2, 5, 0, 3, 1},
025     {4, 5, 3, 2, 0, 1},
026     {4, 3, 0, 5, 2, 1},
027     {1, 0, 3, 2, 5, 4},
028     {1, 3, 5, 0, 2, 4},
029     {1, 5, 2, 3, 0, 4},
030     {1, 2, 0, 5, 3, 4}
031 };
032 
033 class Cube{
034     public:
035     int faces[6];
036     Cube(){}
037 };
038 
039 int n;
040 Cube cubes[4];
041 Cube buffer[4];
042 int mincost;
043 
044 map<string, int> CT; //color table;
045 int colorID;
046 
047 int check(){
048     int T[25];
049     int diff = 0;
050     for ( int f = 0; f < 6; f++ ){
051         for ( int i = 0; i < 25; i++ ) T[i] = 0;
052         
053         for ( int i = 0; i < n; i++ ){
054             T[buffer[i].faces[f]]++;
055         }
056         
057         int maxv = 0;
058         int maxc;
059         for ( int i = 0; i < 25; i++ ){
060             if ( maxv < T[i] ){
061                 maxv = T[i];
062                 maxc = i;
063             }
064         }
065         
066         for ( int i = 0; i < n; i++ ){
067             if ( buffer[i].faces[f] != maxc ) diff++;
068         }
069     }
070     return diff;
071 }
072 
073 void recursive( int pos ){
074     if ( pos == n ){
075         mincost = min( mincost, check() );
076         return;
077     }
078     
079     Cube tmp = buffer[pos];
080     for ( int i = 0; i < 24; i++ ){
081         for ( int f = 0; f < 6; f++ ){
082             buffer[pos].faces[f] = cubes[pos].faces[RT[i][f]];
083         }
084         recursive( pos+1 );
085     }
086 }
087 
088 int compute(){
089     buffer[0] = cubes[0];
090     mincost = 24;
091     recursive(1);
092     return mincost;
093 }
094 
095 int getColor(string color){
096     if ( CT.find(color) == CT.end() ) CT[color] = colorID++;
097     return CT[color];
098 }
099 
100 bool initialize(){
101     cin >> n;
102     if ( n == 0 ) return false;
103     CT = map<string, int>();
104     colorID = 0;
105     string color;
106     for ( int i = 0; i < n; i++ ){
107         for ( int j = 0; j < 6; j++ ){
108             cin >> color;
109             cubes[i].faces[j] = getColor(color);
110         }
111     }
112     return true;
113 }
114 
115 main(){
116     while( initialize() ) cout << compute() << endl;
117 }