Dice Puzzle
2007.09.24 00:08 ACM/ICPC 2004
問題 ACM/ICPC Asia Regional 2004 Ehime: Problem F
概要
側面に数字(1から6)が書かれたサイコロ27個を使い、
3×3×3×のキューブを完成させる。
入力としてキューブの上面と前面の状態が与えられるので、これを満たさなければならない。
また、隣り合うサイコロにおいて、接している側面に書かれている数字の和が7でなければならない。
求めるものは、キューブ右面に見える数字の合計。
解説
バックトラックで総当り探索。
サンプルプログラム
概要
側面に数字(1から6)が書かれたサイコロ27個を使い、
3×3×3×のキューブを完成させる。
入力としてキューブの上面と前面の状態が与えられるので、これを満たさなければならない。
また、隣り合うサイコロにおいて、接している側面に書かれている数字の和が7でなければならない。
求めるものは、キューブ右面に見える数字の合計。
解説
バックトラックで総当り探索。
サンプルプログラム
001 #include<iostream> 002 #include<set> 003 #include<algorithm> 004 using namespace std; 005 006 int RT[24][6] = { 007 {1,2,3,4,5,6}, {1,3,5,2,4,6}, {1,5,4,3,2,6}, {1,4,2,5,3,6}, 008 {4,2,1,6,5,3}, {4,1,5,2,6,3}, {4,5,6,1,2,3}, {4,6,2,5,1,3}, 009 {6,2,4,3,5,1}, {6,4,5,2,3,1}, {6,5,3,4,2,1}, {6,3,2,5,4,1}, 010 {3,2,6,1,5,4}, {3,6,5,2,1,4}, {3,5,1,6,2,4}, {3,1,2,5,6,4}, 011 {5,1,3,4,6,2}, {5,3,6,1,4,2}, {5,6,4,3,1,2}, {5,4,1,6,3,2}, 012 {2,1,4,3,6,5}, {2,4,6,1,3,5}, {2,6,3,4,1,5}, {2,3,1,6,4,5} 013 }; 014 015 int T[3][3], F[3][3], puzzle[27]; 016 set<int> solved; 017 018 int getRight(){ 019 int sum = 0; 020 for ( int i = 2; i < 27; i += 3 ) sum += RT[puzzle[i]][2]; 021 return sum; 022 } 023 024 void recursive( int pos ){ 025 if ( pos == 27 ){ solved.insert(getRight()); return; } 026 int i = (pos%9)/3; 027 int j = (pos%9)%3; 028 int k = pos/9; 029 030 for ( int r = 0; r < 24; r++ ){ 031 if ( i == 0 && T[3-k-1][j] && T[3-k-1][j] != RT[r][0] ) continue; 032 if ( k == 0 && F[i][j] && F[i][j] != RT[r][1] ) continue; 033 if ( i && RT[r][0] + RT[puzzle[k*9+(i-1)*3+j]][5] != 7 ) continue; 034 if ( k && RT[r][1] + RT[puzzle[(k-1)*9+i*3+j]][4] != 7 ) continue; 035 if ( j && RT[r][3] + RT[puzzle[k*9+i*3+(j-1)]][2] != 7 ) continue; 036 puzzle[pos] = r; 037 recursive( pos+1 ); 038 } 039 } 040 041 void compute(){ 042 solved.clear(); 043 recursive(0); 044 if ( solved.size() == 0 ) { cout << 0 << endl; return; } 045 set<int>::iterator p = solved.begin(); 046 cout << *p; 047 for ( p++; p != solved.end(); p++ ) cout << " " << *p; 048 cout << endl; 049 } 050 051 main(){ 052 int tcase; cin >> tcase; 053 for ( int t = 0; t < tcase; t++ ){ 054 for ( int i = 0; i < 3; i++ ) { 055 for ( int j = 0; j < 3; j++ ) cin >> T[i][j]; 056 } 057 for ( int i = 0; i < 3; i++ ) { 058 for ( int j = 0; j < 3; j++ ) cin >> F[i][j]; 059 } 060 compute(); 061 } 062 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |