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

土下座しながら探索中

主に競技プログラミング

AOJ 1249 : Make a Sequence

AOJ

問題リンク: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;
}