Make a Sequence
2007.09.24 00:00 ACM/ICPC 2004
問題 ACM/ICPC Asia Regional 2004 Ehime: Problem B
概要
3次元の○×ゲーム(n目並べ)をシミュレーションし、
勝者と勝負がつくまでの手数を求めよ。
解説
原点から13方向分の単位ベクトルを表す配列を用意すると実装が楽になります。
サンプルプログラム
概要
3次元の○×ゲーム(n目並べ)をシミュレーションし、
勝者と勝負がつくまでの手数を求めよ。
解説
原点から13方向分の単位ベクトルを表す配列を用意すると実装が楽になります。
サンプルプログラム
001 #include<iostream> 002 #include<cassert> 003 using namespace std; 004 #define BLACK 0 005 #define WHITE 1 006 #define SPACE 2 007 int n, m, p; 008 int board[7][7][7], zsize[7][7]; 009 static const int dx[13] = {0, -1, -1, -1, -1, 0, 1, 0, 0, -1, -1, 1, 1}; 010 static const int dy[13] = {1, 1, 0, -1, 0, 0, 0, 1, -1, 1, -1, -1, 1}; 011 static const int dz[13] = {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}; 012 013 bool in( int a ){ return (0 <= a && a < n); } 014 015 int parse( int x, int y, int z, int d ){ 016 int nx, ny, nz; 017 int sum = 0; 018 nx = x; ny = y; nz = z; 019 while( in(nx) && in(ny) && in(nz) && board[nx][ny][nz] == board[x][y][z]){ 020 sum++; 021 nx += dx[d]; ny += dy[d]; nz += dz[d]; 022 } 023 nx = x; ny = y; nz = z; 024 while( in(nx) && in(ny) && in(nz) && board[nx][ny][nz] == board[x][y][z]){ 025 sum++; 026 nx -= dx[d]; ny -= dy[d]; nz -= dz[d]; 027 } 028 return sum - 1; 029 } 030 031 void simulate(){ 032 for ( int x = 0; x < n; x++ ){ 033 for ( int y = 0; y < n; y++ ){ 034 zsize[x][y] = 0; 035 for ( int z = 0; z < n; z++ ) board[x][y][z] = SPACE; 036 } 037 } 038 int move = 0; 039 bool isDraw = true; 040 int x, y; 041 for ( int i = 0; i < p; i++ ){ 042 cin >> x >> y; x--; y--; 043 if ( !isDraw ) continue; 044 board[x][y][zsize[x][y]++] = ((++move)%2); 045 for ( int d = 0; d < 13; d++ ){ 046 if ( parse( x, y, zsize[x][y]-1, d ) >= m ) isDraw = false; 047 } 048 } 049 050 if ( isDraw ) cout << "Draw" << endl; 051 else { 052 cout << ((move%2 == 1) ? "Black" : "White") << " " << move << endl; 053 } 054 } 055 056 main(){ 057 while ( cin >> n >> m >> p, (n || m || p) ) simulate(); 058 }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |