1.5 围棋（难度：★★☆☆☆）

1.5.1 试题

题目描述

小tiger最近迷上了围棋。他对围棋围住对方的棋后能吃掉一大片感到很兴奋，于是整天研究轮到他走的某个局面一步最多能吃到多少个棋子。不过这个围棋棋盘对小tiger来说实在太大了，为了更快地了解该怎么下棋，tiger找到了作为程序设计高手的你，帮他写一个判断吃子的程序，注意小tiger是先手执黑的。

这里简单介绍一下围棋的规则：棋盘上直线紧邻的点上如果有同色棋子存在，这些棋子就相互连接成一个不可分割的整体。直线紧邻的点上如果有异色棋子存在，此处的气便不存在。棋子如失去所有的气，就不能在棋盘上存在。如果某方下子后，对方棋子无气，或双方棋子都呈无气状态，则应立即提取对方无气之子。

输入格式

文件第1行为两个整数n，m（1≤n≤20，1≤m≤20），代表棋盘的大小。

下面n行每行m个整数，用空格隔开，代表现有的棋盘状态，只包括0，−1，1三个整数，分别代表该点被空格、白棋或黑棋占据。

输出格式

对每组数据，输出黑棋的最多吃子数与下该棋子的坐标。默认左下角为（1，1），第一个数为横向，从左向右递增，第二个数为纵向，从下到上递增（即与二维坐标系相同）。如果有多个吃子数量相同的点，则以坐标X轴小者优先，再以Y轴小者优先。如果吃不了子，则输出一行“0 0 0”。

输入样例

3 3

0 1 0

1-1 0

0 1 0

输出样例

1 3 2

1.5.2 题目分析和算法实现

本题描述了一个n*m的围棋棋盘上的一个棋局，根据棋局选择一个能吃到最多白棋的位置放下黑棋。由于不用考虑以后的棋局怎么走，所以直接枚举棋盘的每一个能放黑棋的位置，然后做一次floodfill（种子染色，详见参考文献[2]）就可以了。原本此题的数据规模是200*200的，目的是要考查直接对每个位置枚举的算法，以及实现非递归floodfill（直接递归floodfill200*200 层很容易就会超出栈空间），后来题目定位为简单题，于是规模就改为与标准围棋盘差不多的20*20。这主要是担心一些选手不太了解围棋的提子规则，所以对此题加了比较多的样例说明，不过通过本题的样例，选手大致可以知道围棋的提子规则了。

直接的做法就是枚举每个可放黑棋的位置，然后对放了黑棋的点的四个方向（如果是白棋）对白棋做一次floodfill，看看整块白棋的所有边缘（包括白棋块的内部）是否都被黑棋或者棋盘边缘包围，统计这四个方向的floodfill结果，如果被包围则返回白棋总数，否则返回非包围标志，最后输出一个能吃到最多白棋的位置即可。

对于比较大的数据，如200*200的规模，这样枚举所有能放黑棋的位置再做floodfill，很容易写成（200*200）*（200*200），就会超时，所以要改一下想法，直接对整个棋盘的白棋floodfill一次。对该块只剩一个空位置的返回该块的白棋总数、空位置坐标，代表这一块白棋能通过在空位置坐标上放一个黑棋而被整块吃掉。最后统计一下棋盘上每个坐标记录过的“能吃白棋数”，就可以得解了。这样的复杂度只是200*200，下面的程序给出的就是这个版本。

最后说说一些特殊情况，测试数据里有一些目标靠棋盘边缘的数据，如果floodfill实现得不好会出现程序运行时出错；有一些是放一个黑棋能吃掉两块或以上独立的白棋的，还有整个棋盘全部都是白棋只有一个位置空着的，这些数据都是考查选手程序的严谨性的。有兴趣的选手可以尝试测试一下规模在万级以上的数据，就可以体会出floodfill过程的递归与非递归实现的差异。

1.5.3 参考程序及程序分析

#include＜stdio.h＞
#include＜string.h＞
const long maxn=206;
long bj;                                    //表示floodfill时遇到的空位个数
long markx,marky,bestx,besty,tot,tetot,n,m,tex,tey;
long map[maxn][maxn],mark[maxn][maxn],outer[maxn][maxn];
//map为棋盘初始状态，mark为floodfill的标记，outer记录某空位的吃子数
void search(void){
    if (map[tex][tey]==-1){                 //白棋则继续扩展
        mark[tex][tey]=1;tetot++;          //记(tex,tey)为已扩展，累计已扩展棋子数
        //向四个方向floodfill
        if (tex-1＞=1&&mark[tex-1][tey]==0) tex--,search(),tex++;
        if (tex+1＜=n&&mark[tex+1][tey]==0) tex++,search(),tex--;
        if (tey-1＞=1&&mark[tex][tey-1]==0) tey--,search(),tey++;
        if (tey+1＜=m&&mark[tex][tey+1]==0) tey++,search(),tey--;
    }else{
        if (map[tex][tey]==0){              //空位
            if (bj==0){                     //第一个空位
                bj++;markx=tex;marky=tey;  //记录空位坐标
            }else if (bj==1){               //找到第二个空位
                if (markx!=tex||marky!=tey) bj=2;
//空位位置不同则不可能吃掉这片白子
            }
        }
    }
}
void run(long x,long y){
    bj=0;markx=0;marky=0;                   //初始化
    tex=x;tey=y;tetot=0;search();          //由(tex,tey)点进行扩展
    if (bj==1&&tetot＞tot){                  //仅有一个空位，累计该空位放黑子的吃子数
        outer[markx][marky]+=tetot;
    }
}
int main(){
    long i,j;
    freopen("go.in","r",stdin);
    freopen("go.std","w",stdout);
    while (scanf("%ld%ld",&n,&m)!=EOF){                     //输入棋盘大小
        //初始化
        memset(map,0,sizeof(map));
        memset(mark,0,sizeof(mark));
        memset(outer,0,sizeof(outer));
        for (i=1;i＜=n;i++){
            for (j=1;j＜=m;j++) scanf("%ld",&map[i][j]);    //输入棋盘
        }
        tot=0;bestx=0;besty=0;
        for (j=1;j＜=m;j++){
            for (i=n;i＞=1;i--){
                if (!mark[i][j]&&map[i][j]==-1) run(i,j);
//寻找白棋进行floodfill
            }
        }
        //枚举每一个格
        for (j=1;j＜=m;j++){
            for (i=n;i＞=1;i--){
                if (outer[i][j]＞tot){                     //寻找最多吃子位置
                    tot=outer[i][j];bestx=i;besty=j;
                }
            }
        }
        if (tot==0) printf("0 0 0\n");                    //无解
        else printf("%ld %ld %ld\n",tot,besty,n-bestx+1);  //输出最优解及最优位置
    }
    return 0;
}

1.5.4 部分测试数据和输出结果

测试数据

3 3

0 1 0

1-1 0

0 1 0

3 3

0 0 0

1 0 0

-1 0 0

3 4

-1 1-1-1

-1 0-1-1

-1-1 0-1

5 6

-1 1 1-1 0 1

0 0-1 1 1 1

-1 1-1-1 1-1

1 1-1 1-1-1

-1-1-1 1 0 1

输出结果

1 3 2

1 2 1

0 0 0

7 2 4