Friday, June 10, 2011

852 - Deciding victory in Go


#include<iostream>
#include<cstdio>
#include<cstring>
#define M 9
using namespace std;

char graph[M][M+1];
bool black,white;
int size;
int next[8][2]={{-1,0},{0,-1},{1,0},{0,1}};
void DFS_Visit(int,int);

int main()
{
    int t,i,j,pw,pb,k;
    //freopen("in.txt","r",stdin);
    scanf("%d\n",&t);

    for(k=0;k<t;k++)
    {
        for(i=0;i<M;i++)
            gets(graph[i]);

        pw = pb = 0;
        for(i=0;i<M;i++)
            for(j=0;j<M;j++)
                switch(graph[i][j])
                {
                case 'O':
                    pw++;
                    break;
                case 'X':
                    pb++;
                    break;
                case '.':
                    size = 0;black=white=false;
                    DFS_Visit(i,j);
                    if(black&&white)continue;
                    else if(black)pb+=size;
                    else if(white)pw+=size;
                    break;
                }
    printf("Black %d White %d\n",pb,pw);
    }
    return 0;
}

void DFS_Visit(int x,int y)
{
    int i,j,tx,ty,xx,yy;
    graph[x][y]='*';
   
    for(j=0;j<4;j++)
    {
        xx=x+next[j][0],yy=y+next[j][1];
        if(xx>=0&&xx<M&&yy>=0&&yy<M)
            if(graph[xx][yy]=='X')black = true;
            else if(graph[xx][yy]=='O')white = true;
    }

    size++;
    for(i=0;i<4;i++)
    {
        tx=x+next[i][0],ty=y+next[i][1];
        if(tx>=0&&tx<M&&ty>=0&&ty<M&&graph[tx][ty]=='.')
        {
            DFS_Visit(tx,ty);
        }
    }
}

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.