天棋哥哥大战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[][];

int vis[][];

int dr[][]={{,},{,},{-,},{,-} };

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>= && x< && y>= && y<) return ;

      return ;

}

int bfs(int x,int y)

{

    vis[x][y]=;

    int num=;

    int flag=;

    queue<node> Q;

    Q.push(node(x,y));

    while(!Q.empty())

    {

        node p=Q.front();

        Q.pop();

       for(int i=;i<;i++)

       {

           int xx=p.x+dr[i][];

           int yy=p.y+dr[i][];

           if (!check(xx,yy)) continue;

           if (mp[xx][yy]=='.') flag=;

           if (mp[xx][yy]=='O' && !vis[xx][yy])

           {

               num++;

               vis[xx][yy]=;

               Q.push(node(xx,yy));

           }

       }

    }

  if (!flag) return num;

    else return ;

}

void findpos(int x,int y)

{

    vis[x][y]=;

    queue<node> Q;

    Q.push(node(x,y));

    while(!Q.empty())

    {

        node p=Q.front();

        Q.pop();

       for(int i=;i<;i++)

       {

           int xx=p.x+dr[i][];

           int yy=p.y+dr[i][];

           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]=;

       }

    }

  return;

}

int main()

{

   while(~scanf("%s",&mp[]))

   {

        for(i=;i<;i++)

         scanf("%s",&mp[i]);

         memset(vis,,sizeof(vis));

         sx.clear();

         so.clear();

         for(i=;i<;i++)

            for(j=;j<;j++)

             if (mp[i][j]=='O')

            {

                so.push_back(node(i,j));

                if (!vis[i][j]) findpos(i,j);

            }

        ans=;

        for(i=;i<sx.size();i++)

        {

            mp[sx[i].x][sx[i].y]='X';

            num=;

            memset(vis,,sizeof(vis));

            for(j=;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 ;

}

/*

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

....XXX............

...XOOOX...........

....XX.OX..........

....XOO............

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

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

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

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

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

.................OX

................OXO

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

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

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

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

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

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

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

*/