Make a Sequence

問題 ACM/ICPC Asia Regional 2004 Ehime: Problem B

概要

３次元の○×ゲーム（ｎ目並べ）をシミュレーションし、
勝者と勝負がつくまでの手数を求めよ。

解説

原点から１３方向分の単位ベクトルを表す配列を用意すると実装が楽になります。

サンプルプログラム

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 }