学步园

不能一次消除一行或一列，只能一次消除相邻的，怎么办？

实质上只是需要一步预处理。扫描一遍输入的矩阵，把每行和每列中相邻的障碍物看成一个点，记录一下，然后加边。这样就转化成了poj3041:                 http://blog.csdn.net/challenchenzhipeng/article/details/7687918

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 2000
int match[maxn];
int map[maxn][maxn];
bool v[maxn];
int nx,ny;//x的数目和y的数目
char s[52][52];
int cx[52][52];
int cy[52][52];
int n,m;
bool dfs(int p)
{
    int i;
    for(i=1;i<=ny;i++)
    {
        if(map[p][i]&&!v[i])
        {
            v[i]=1;
            if(match[i]==-1||dfs(match[i]))
            {
                match[i]=p;
                return 1;
            }
        }
    }
    return 0;
}
int Hungry()
{
    int i;
    int ans=0;
    for(i=1;i<=nx;i++)
    {
        memset(v,0,sizeof(v));
        if(dfs(i))
            ans++;
    }
    return ans;
}
int main()
{
    int i,j,k;
    scanf("%d%d",&n,&m);
    getchar();
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            s[i][j]=getchar();
        }
        getchar();
    }
    nx=0;
    ny=0;
    for(i=1;i<=n;i++)//在水平方向上查找连续的'*'
    {
        j=1;
        while(j<=m)
        {
            if(s[i][j]=='*')
            {
                nx++;
                while(s[i][j]=='*')
                {
                    cx[i][j]=nx;//离散化，将横向且连续(一个或以上)的'*'看成一个点并对其进行编号
                    j++;
                }
            }
            else j++;
        }
    }
    for(j=1;j<=m;j++)//在垂直方向上查找连续的'*'
    {
        i=1;
        while(i<=n)
        {
            if(s[i][j]=='*')
            {
                ny++;
                while(s[i][j]=='*')//离散化，将竖向且连续(一个或以上)的'*'看成一个点并对其进行编号
                {
                    cy[i][j]=ny;
                    i++;
                }
            }
            else i++;
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(s[i][j]=='*')
            {
                map[cx[i][j]][cy[i][j]]=1;
            }
        }
    }
    memset(match,-1,sizeof(match));
    printf("%d\n",Hungry());
    system("pause");
    return 0;
}