给你一个地图，每个天线最多可以覆盖相邻的两个房子，问你最少用多少个天线可以覆盖全部房子。

思路：先对所有的房子编号，然后对一个房子x如果它正下方或者右方有房子y, 那么e[x][y]=e[y][x]=1;

那么最大匹配ans/2就是能够覆盖两个房子的天线数，那么剩下的房子，就每一个都必须用一个天线来匹配。

能够覆盖两个房子的天线数： ans/2
单独覆盖一个房子的天线数： 所有的点N-ans
所有的房子数：N-ans+ans/2 = N-ans/2

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>

using namespace std;

int n,m;//顶点数n和边的数目m
int e[510][510];//保存一个无向图
int book[510];//每次都标记那个去了和那个没去
int match[510];//标记匹配
#define inf 9999//假设的无穷大
int dfs (int u)
{
    int i;
    for (i=1;i<=n;i++)
    {
        if (book[i]==0&&e[u][i]==1)//这个点在同一次上没去过，而且他们能联通
        {
            book[i]=1;//这个点已经尝试过了
            if (match[i]==0||dfs(match[i]))//这个点还没有被匹配，
                //或者，他可以匹配其他的人
            {
               //他们就能够匹配
                match[i]=u;//判断哪个，就是修改那个
                //match[u]=i;不用的，错误的
                return 1;
            }
        }
    }
    return 0;
}

int work()
{
    memset(match, 0, sizeof(match));
    int i_count=0;
    for (int i=1;i<=n;i++)//尝试遍历每一个顶点
    {
        memset (book,0,sizeof(book));
        if (dfs(i))
        {
            i_count++;//若能找到新的匹配，就++
        }
    }

    return i_count;
}

char mp[50][50];
int id[50][50];
int main ()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf ("%d%d",&n,&m);//输入顶点数n和边的数目m
        memset(e, 0, sizeof(e));
        memset(id, 0, sizeof(id));
        for(int i=0;i<n;i++)
        {
            scanf("%s",mp[i]);
        }
        int N=n;
        n=0;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(mp[i][j]=='*')
                {
                    id[i][j]=++n;
                }
            }
        }
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<strlen(mp[i]);j++)
            {
                if(mp[i][j]=='*')
                {
                    if(i+1<N&&mp[i+1][j]=='*')
                    {
                        //cout<<id[i][j]<<" "<<id[i+1][j]<<endl;
                        e[id[i][j]][id[i+1][j]]=1;
                        e[id[i+1][j]][id[i][j]]=1;
                    }
                    if(j+1<m&&mp[i][j+1]=='*')
                    {
                        e[id[i][j]][id[i][j+1]]=1;
                        e[id[i][j+1]][id[i][j]]=1;
                    }
                }
            }
        }

        int ans=work();
        printf ("%d\n",n-ans/2);
    }

    return 0;
}