AOJ : 1249 - Make a Sequence

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1249
三目並べを立体にしたようなゲームで遊びます.
2人のプレーヤーが交互に, N*Nの棒のどれかにボールを差し込みます.
先に, M個のボールを直線状に並べた人が勝ちです.
全てのボールを置き終わっても, 勝者がいない場合はDrawです.

アルゴリズム

実装するだけです.

プログラム

int n,m,q;
int X[400],Y[400];
int h[7][7],t[7][7][7];

int dx[] = { 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1};
int dy[] = { 0, 1, 0, 1,-1, 0, 0, 1, 1, 1, 1,-1,-1};
int dz[] = { 0, 0, 1, 0, 0, 1,-1, 1,-1, 1,-1, 1,-1};

void putBall(int x,int y,int color){
  t[y][x][h[y][x]] = color;
  h[y][x]++;
}

bool judge(int color){
  rep(x,n){
    rep(y,n){
      rep(z,n){
        rep(d,13){


          int xx = x;
          int yy = y;
          int zz = z;
          int i = 0;

          while(0 <= xx && xx < n && 0 <= yy && yy < n &&
                0 <= zz && zz < n && t[yy][xx][zz] == color){
            xx += dx[d];
            yy += dy[d];
            zz += dz[d];
            i++;
          }
          if(i >= m) return true;
        }
      }
    }
  }
  return false;
}

int main(void){
  while(cin>>n>>m>>q,n||m||q){
    memset(h,0,sizeof(h));
    memset(t,-1,sizeof(t));

    rep(i,q){
      cin>>X[i]>>Y[i];
      X[i]--;
      Y[i]--;
    }

    int color = 0;
    bool printFlg = false;
    rep(i,q){
      putBall(X[i],Y[i],color);

      if(judge(color)){
        printFlg = true;
        cout<<(color ? "White " : "Black ")<<i+1<<endl;
        break;
      }
      color = !color;
    }
    if(!printFlg) cout<<"Draw\n";
  }
}