学步园

/*
    poj 3020 最小路径覆盖
    题目一开始没看懂 囧
    参考了网上的代码，这是个最小路径覆盖的问题
    o代表不需要覆盖天线的地方 *代表需要覆盖天线的地方
    一根天线可以惠及两个相邻的*点，问最少需要多少天线才能把所有*点覆盖完
    
    无向二分图的最小路径覆盖=点数-最大匹配/2
    建模过程：将每个*点看做点，进行拆点
*/

#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 405
int T;
int h,w;
int count;
int dir[4][2]={0,1,1,0,-1,0,0,-1};
int map[41][11];
int link[maxn][maxn];
bool vis[maxn];
int match[maxn];
bool find(int x)
{
    for(int i=1; i<=count-1; i++)
    {
        if(!vis[i] && link[x][i])
        {
            vis[i]=1;
            if(find(match[i]) || match[i]==0)
            {
                match[i]=x;
                return true;
            }
        }
    }
    return false;
}
int MMG()
{
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=1; i<=count-1; i++)
    {
        memset(vis,0,sizeof(vis));
        if(find(i))    ans++;
    }
    return ans;
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&h,&w);
        memset(map,0,sizeof(map));
        memset(link,0,sizeof(link));
        char c[maxn];
        count=1;
        for(int i=1; i<=h; i++)
        {
            scanf("%s",c);
            for(int j=1; j<=w; j++)
                c[j-1]=='*'?map[i][j]=count++:0;
        }

//        for(int i=1; i<=h; i++)
//        {
//            for(int j=1; j<=w; j++)
//                printf("%d",map[i][j]);
//            printf("\n");
//        }
//        while(1){}

        for(int i=1; i<=h; i++)
            for(int j=1; j<=w; j++)
            {
                if(map[i][j])
                {
                    for(int k=0; k<4; k++)
                    {
                        int x=i+dir[k][0],y=j+dir[k][1];
                        if(map[x][y])
                            link[map[i][j]][map[x][y]]=1;
                    }
                }
            }

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