読者です 読者をやめる 読者になる 読者になる

日々精進

aikoと旅行とプログラミング

【AOJ 1249】Make a Sequence

問題

Make a Sequence | Aizu Online Judge

方針

  • 置くたびにm個以上つながっているかを調べる.
  • 縦横斜めの3方向を探索するので, dx, dy, dzという配列を用意しておき3重ループする.

コード

#include<bits/stdc++.h>
 
 
#define rep(i, n) REP(i, 0, n)
#define REP(i, a, n) for(int i = a ; i < (int)n ; i++)
#define m0(x) memset(x, 0, sizeof(x))
#define EMPTY -1
 
using namespace std;
 
typedef pair<int, int> pii;
 
int dx[3] = {-1, 0, 1};
int dy[3] = {-1, 0, 1};
int dz[3] = {-1, 0, 1};
 
int n, m, p;
int peg[10][10][10];
pii coordinate[350];
 
int idx;
 
bool check(int x, int y, int z){
 
  rep(i, 3){
    rep(j, 3){
      rep(k, 3){
     
        if(dx[i] == 0 && dy[j] == 0 && dz[k] == 0) continue;
     
        int len = 1;
        int sgn = 1;    
        rep(l, 2){
        int nx = x; int ny = y; int nz = z;
          while(true){      
            nx += (sgn * dx[i]); ny += (sgn * dy[j]); nz += (sgn * dz[k]);         
            if(nx < 0 || n <= nx || ny < 0 || n <= ny || nz < 0 || n <= nz) break;  
            if(peg[x][y][z] == peg[nx][ny][nz]) len++;
            else break;   
          }
          if(len >= m) return true;
          sgn *= (-1);
        }
 
        if(len >= m) return true;    
      }
    }
  }
  return false;
}
 
int getTurn(){
  memset(peg, EMPTY, sizeof(peg));
   
  rep(i, p){
     
    int x = coordinate[i].first; int y = coordinate[i].second; 
    bool ret = false;
    bool flag = false;
    rep(z, n){
      if(peg[x][y][z] == EMPTY){
        peg[x][y][z] = i % 2;
        idx = i;
        ret = check(x, y, z); // 何個連続しているか調べる
        flag = true;
        break;
      }      
    }
    if(!flag) return 0;
    if(ret) return i+1;
  }
 
  return 0;
}
 
signed main(){
   
  while(cin >> n >> m >> p, n || m || p){
    rep(i, p){
      cin >> coordinate[i].first >> coordinate[i].second;     
      coordinate[i].first--;
      coordinate[i].second--;
    }
     
    int ret = getTurn();
    if(ret == 0) cout << "Draw" << endl;
    else if(ret % 2 != 0) cout << "Black " << ret << endl;
    else cout << "White " << ret << endl;        
  }
}