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"; } }