Colored Cubes
2007.08.24 22:22 ACM/ICPC 2005
[問題] 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 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |