ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1249 Make a Sequence

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1249

○×ゲームを3次元でやろうみたいな問題です。

○| |○
───
×|×|○
───
×| |○

↑2次元だとこんなかんじ


・解法
やるだけ問題です。

連続に並んでいるかを判定させるとき、
static const int dx={1,0,0,1,1,0,1, 1, 0,-1, 1, 1,-1};
static const int dy
={0,1,0,1,0,1,1,-1, 1, 0, 1,-1, 1};
static const int dz[]={0,0,1,0,1,1,1, 0,-1, 1,-1, 1, 1};
のようにあらかじめ各方向について準備しておけば楽に実装できます。


・ソースコード

#include<iostream>
#include<cstring>
#include<map>
#include<cstdio>
using namespace std;

#define f first
#define s second
static const int dx[]={1,0,0,1,1,0,1, 1, 0,-1, 1, 1,-1};
static const int dy[]={0,1,0,1,0,1,1,-1, 1, 0, 1,-1, 1};
static const int dz[]={0,0,1,0,1,1,1, 0,-1, 1,-1, 1, 1};

//Black = 0, White = 1
int n,m,p;
int pegs[7][7][7];
pair<int,int> put[7*7*7];

bool check(int x, int y, int z){
  for(int k = 0 ; k < 13 ; k++){
    int seq = 1;
    int nx = x;
    int ny = y;
    int nz = z;
    while(true){
      nx += dx[k];
      ny += dy[k];
      nz += dz[k];
      if(!(0<=nx&&nx<n && 0<=ny&&ny<n && 0<=nz&&nz<n)) break;
      if(pegs[nx][ny][nz]==pegs[x][y][z]) seq++;
      else break;
    }
    nx = x;
    ny = y;
    nz = z;
    while(true){
      nx -= dx[k];
      ny -= dy[k];
      nz -= dz[k];
      if(!(0<=nx&&nx<n && 0<=ny&&ny<n && 0<=nz&&nz<n)) break;
      if(pegs[nx][ny][nz]==pegs[x][y][z]) seq++;
      else break;
    }
    if(seq >= m) return true;
  }
  return false;
}

int solve(){
  memset(pegs,-1,sizeof(pegs));
  for(int i = 0 ; i < p ; i++){
    int x = put[i].f;
    int y = put[i].s;
    bool canPut = false;
    bool win = false;
    for(int z = 0 ; z < n ; z++){
      if(pegs[x][y][z]==-1){
        pegs[x][y][z] = i % 2;
        canPut = true;
        win = check(x,y,z);
        break;
      }
    }
    if(!canPut) break;
    if(win) return i+1;
  }
  return 0;
}

int main(){
  while(cin >> n >> m >> p, (n|m|p)){
    for(int i = 0 ; i < p ; i++){
      int x,y;
      scanf("%d%d",&x,&y);
      put[i].f = x-1;
      put[i].s = y-1;
    }
    int ans = solve();
    if(ans==0) puts("Draw");
    else if(ans%2==1) printf("Black %d\n",ans);
    else if(ans%2==0) printf("White %d\n",ans);
  }
  return 0;
}