AOJ 1249 : Make a Sequence
問題リンク:Make a Sequence | Aizu Online Judge
問題概要:
図の様なn*nのグラフ上にp回黒と白のボールを交互に刺す
8方向をみて同じ色のボールがm個以上そろっていればその色の人の勝利となる
勝利した人とそのターンを出力せよ
使用した言語:C++
解法:
グラフが小さいので愚直にやるだけでよい
int d[] = {0,1,-1}という配列を用意して3重ループで全方向を確認し、条件を満たしていればその人とターンを記録する
そろっている色のカウントはちゃんと一番端っこから始めること
コード:
#include<iostream> #include<algorithm> #define B 1 #define W 2 #define rep(i,n) for(int i=0;i<n;i++) using namespace std; short d[] = {0,1,-1}; int n,m,p; short G[7*7*7+1][8][8]; bool check(int x,int y,int z) { for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { for(int k=0;k<3;k++) { if(i+j+k == 0) continue; short dx = d[k],dy = d[j],dz = d[i]; short c = G[z][y][x]; short cnt = 0; short nx,ny,nz; nx = ny = nz = 0; while((0 <= x+nx && x+nx < n) && (0 <= y+ny && y+ny < n) && (0 <= z+nz && z+nz < n) && G[z+nz][y+ny][x+nx] == c) nz-=dz,ny-=dy,nx-=dx; nz+=dz,ny+=dy,nx+=dx; while((0 <= x+nx && x+nx < n) && (0 <= y+ny && y+ny < n) && (0 <= z+nz && z+nz < n) && G[z+nz][y+ny][x+nx] == c) cnt++,nz+=dz,ny+=dy,nx+=dx; if(cnt >= m) return true; } } } return false; } int main() { while(cin >> n >> m >> p,n|m|p) { rep(i,p+1) rep(j,n+1) rep(k,n+1) G[i][j][k] = 0; int found = -1; rep(i,p) { int x,y,z = 0; cin >> x >> y; x--,y--; while(G[z][y][x]!=0) z++; G[z][y][x] = i%2?W:B; if(found == -1) if(check(x,y,z)) found = i; } if(found == -1) cout << "Draw" << endl; else found%2?cout << "White " << found+1 << endl:cout << "Black " << found+1 << endl; } return 0; }