题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=654

AC一百道水题，不如AC一道难题来的舒服。

题意：一个n*m地图。*代表草地，#代表墙，o代表空地，要再图中的o处放机器人，机器人能够攻击（上下左右）4个方向，攻击范围无限长，并且机器人不能相互攻击，草地不能放置机器人，且机器人的攻击能够穿过草地，可是机器人的攻击不能穿过墙，比方 “   *o#o  ”这一行就能够放两个机器人，” o*oo
“ 这一行就仅仅能放一个，问最多能放多少个机器人？

刚学了二分图，二分图的水题做了有几个。不须要来练手了，对于这个题。看懂题意后知道是二分图的最大独立集合。可是难点是怎么建图。

昨天晚上看的这道题目，一点思路也没有。回宿舍后想了又想，想到怎么建图，今天敲了。WA n次，查了一下题解。建图方式没有错，仅仅是我漏了一点就是，仅仅进行了横向分块当做X集合，剩余点默觉得Y集合。

。。

思路：採用分块的思想进行建图。什么是块？联系题意。块就攻击范围能够达到的就是一块，“ o*oo ”这就是块，并且是一块，“ *o#o
”，这就是两块。 通俗点说就是，地图的这一行被墙隔开且有空地的连续区域称作”块“。当然，依照题意。在一个块中，最多仅仅能放置一个机器人，纵向也是如此分块，对块进行编号。横向分块的全部编号为X集合，纵向的全部编号为Y集合，当然存在同一个” o“点被两次编号过，那么建一条边就好了。

include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <math.h>

#define init(a) memset(a,0,sizeof(a))

#define PI acos(-1,0)

using namespace std;

const int maxn = 55;

const int maxm = 2600;

#define lson left, m, id<<1

#define rson m+1, right, id<<1|1

#define min(a,b) (a>b)?b:a

#define max(a,b) (a>b)?a:b

int mar[maxn][maxn],mac[maxn][maxn];

int G[maxm][maxm];

int line[maxm];

char MAP[maxn][maxn];

bool vis[maxm];

int X,Y;

int DFS(int u)

{

    for(int v = 1;v<=Y;v++)

    {

        if(G[u][v]==1 && !vis[v])

        {

            vis[v] = 1;

            if(line[v]==-1 || DFS(line[v]))

            {

                line[v] = u;

                return 1;

            }

        }

    }

    return 0;

}

int K_M()

{

    memset(line,-1,sizeof(line));

    int ans = 0;

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

    {

        init(vis);

        ans += DFS(i);

    }

    return ans;

}

void Creat_G(int n,int m)

{

    for(int i = 0;i<n;i++)  //横向分块当做X集合

        {

            for(int j = 0;j<m;j++)

            {

                if(MAP[i][j]=='o')

                {

                    X++;

                    while(j<m && MAP[i][j]!='#')

                    {

                        mar[i][j]=X;//处于同一块的空地或草地编号是一样的

                        j++;

                    }

                }

            }

        }

        for(int i = 0;i<m;i++)//纵向分块当做Y集合

        {

            for(int j = 0;j<n;j++)

            {

                if(MAP[j][i]=='o')

                {

                    Y++;

                    while(j<n && MAP[j][i]!='#')

                    {

                        mac[j][i] = Y;

                        j++;

                    }

                }

            }

        }

}

int main()

{

    int t,n,m;

    scanf("%d",&t);

    for(int Case = 1;Case <=t;Case++)

    {

        init(G); init(mar);init(mac);

        X = 0, Y = 0;

        scanf("%d%d",&n,&m);

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

            scanf("%s",MAP[i]);

        Creat_G(n,m);//分块

        for(int i = 0;i<n;i++) //建图

        {

            for(int j = 0;j<m;j++)

            {

                if(MAP[i][j]=='o')

                {

                    G[mar[i][j]][mac[i][j]] = 1;//构建块与块的连通

                }

            }

        }

       int ans = K_M();

        printf("Case :%d\n%d\n",Case,ans);

    }

    return 0;

}