天棋哥哥大战AlphaGo

Time Limit: 1 Sec Memory Limit: 128 MB

Submit: 20 Solved: 9

[Submit][Status][Web Board]

Description

3月15日，人机围棋大战巅峰对决在韩国首尔落下帷幕。五番棋的最后一局中，韩国著名棋手李世乭尽管与人工智能“AlphaGo”缠斗至官子阶段，但在双双进入读秒后最终还是投子认输，以总比分1∶4结束了这场举世瞩目的人机大战。

100年后的某一天，天棋哥哥为了给李世乭报仇，挽回人类尊严，代表人类向AlphaGo发起了挑战。

100年后的AlphaGo比现在强了几百倍，谷歌公司允许天棋哥哥携带一个程序与AlphaGo对战。

为了能战胜AlphaGo，现在请你帮助天棋哥哥写一个程序来判断他这一步落子后，最多能提几子。

提子规则如下：

中国围棋棋盘可以看做一个19*19的网格，每一个网格都可以下棋子。

【棋子的气】

一个棋子在棋盘上，与它直线紧邻的空点是这个棋子的“气”。

直线紧邻的点上如果有同色棋子存在，这些棋子就相互连接成一个不可分割的整体。

直线紧邻的点上如果有异色棋子存在，此处的气便不存在。棋子如失去所有的气，就不能在棋盘上存在。

【提子】

把无气之子清理出棋盘的手段叫“提子”。提子有二种：

1、下子后，对方棋子无气，应立即提取对方无气之子。

2、下子后，双方棋子都呈无气状态，应立即提取对方无气之子。

现在，给出一个局面，轮到天棋哥哥下，请计算他落子后最多能提多少子。

Input

每组测试数据19行，每行为长度19的字符串

'.'代表空格，'X'代表天棋哥哥，'O’代表AlphaGo

Output

输出一个数字，代表最多能提几子。

Sample Input

...................

....XX.............

...XOOX............

.....X.............

....X..............

.....O.............

......O............

...................

....XX.............

...XO.X............

.....X.............

....X..............

.....O.............

......O............

...................

..................X

.................XO

..................O

..................X

...................

Sample Output

#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<deque>
using namespace std;

int ans,i,j,num;
char mp[20][20];
int vis[20][20];
int dr[4][2]={{1,0},{0,1},{-1,0},{0,-1} };

struct node
{
    int x,y;
    node(int a,int b){x=a; y=b;}
};
deque<node> sx,so;

bool check(int x,int y)
{
    if (x>=0 && x<19 && y>=0 && y<19) return 1;
      return 0;
}

int bfs(int x,int y)
{
    vis[x][y]=1;
    int num=1;
    int flag=0;
    queue<node> Q;
    Q.push(node(x,y));
    while(!Q.empty())
    {
        node p=Q.front();
        Q.pop();
       for(int i=0;i<4;i++)
       {
           int xx=p.x+dr[i][0];
           int yy=p.y+dr[i][1];
           if (!check(xx,yy)) continue;
           if (mp[xx][yy]=='.') flag=1;
           if (mp[xx][yy]=='O' && !vis[xx][yy])
           {
               num++;
               vis[xx][yy]=1;
               Q.push(node(xx,yy));
           }
       }
    }
  if (!flag) return num;
    else return 0;
}

void findpos(int x,int y)
{
    vis[x][y]=1;
    queue<node> Q;
    Q.push(node(x,y));
    while(!Q.empty())
    {
        node p=Q.front();
        Q.pop();
       for(int i=0;i<4;i++)
       {
           int xx=p.x+dr[i][0];
           int yy=p.y+dr[i][1];
           if (!check(xx,yy)) continue;
           if (mp[xx][yy]=='O' && !vis[xx][yy]) Q.push(node(xx,yy));
           if (mp[xx][yy]=='.' && !vis[xx][yy]) sx.push_back(node(xx,yy));
           vis[xx][yy]=1;
       }
    }
  return;
}

int main()
{
   while(~scanf("%s",&mp[0]))
   {
        for(i=1;i<19;i++)
         scanf("%s",&mp[i]);

         memset(vis,0,sizeof(vis));
         sx.clear();
         so.clear();
         for(i=0;i<19;i++)
            for(j=0;j<19;j++)
             if (mp[i][j]=='O')
            {
                so.push_back(node(i,j));
                if (!vis[i][j]) findpos(i,j);
            }

        ans=0;
        for(i=0;i<sx.size();i++)
        {
            mp[sx[i].x][sx[i].y]='X';
            num=0;
            memset(vis,0,sizeof(vis));
            for(j=0;j<so.size();j++)
                if(!vis[so[j].x][so[j].y])
                          num+=bfs(so[j].x,so[j].y);
            ans=max(ans,num);
            mp[sx[i].x][sx[i].y]='.';
        }

         printf("%d\n",ans);
   }

    return 0;
}
/*
...................
....XXX............
...XOOOX...........
....XX.OX..........
....XOO............
.....XX............
......O............
...................
...................
..................O
.................OX
................OXO
.................XO
..................O
..................X
...................
...................
...................
...................
*/