题意：每个 ‘*’都需要一个1*2的东西覆盖，问最少需要多少个1*2的东西来覆盖这些‘*’

#include<stdio.h>

#include<string.h>

#include<queue>

using namespace std;

const int MAXN = 1005;///处理后点的个数

const int MAXM = 50;///原图大小

const int oo = 1e9+7;

char G[MAXM][MAXM]; int N, M;///保存原图

int  Index[MAXM][MAXM];///给点编号

struct Edge{int v, next;}e[MAXN*4];

int Head[MAXN], cnt;///处理后的边

int Mx[MAXN], My[MAXN];///记录与之匹配的点

int used[MAXN], dx[MAXN], dy[MAXN];///dx,dy记录DFS后的深度

int depth, NX;///款搜的深度，和点的个数

void InIt()

{///初始化

    NX = cnt = 0;

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

    memset(Mx, false, sizeof(Mx));

    memset(My, false, sizeof(My));

}

void AddEdge(int u, int v)

{///添加边

    e[cnt].v = v;

    e[cnt].next = Head[u];

    Head[u] = cnt++;

}

bool BFS()

{///广搜求出层次，并且判断是否有增广路存在

    queue<int> Q;

    depth = oo;

    memset(dx, false, sizeof(dx));

    memset(dy, false, sizeof(dy));

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

    {

        if( Mx[i] == false )

        {

            dx[i] = true;

            Q.push(i);

        }

    }

    while(Q.size())

    {

        int u = Q.front(); Q.pop();

        if( dx[u] > depth )break;///已经发现上层存在增广路

        for(int j=Head[u]; j!=-1; j=e[j].next)

        {

            int v = e[j].v;

            if( dy[v] == false )

            {

                dy[v] = dx[u] + 1;

                if(My[v] == false)

                    depth = dy[v];

                else

                {

                    dx[ My[v] ] = dy[v] + 1;

                    Q.push( My[v] );

                }

            }

        }

    }

    return depth != oo;

}

bool DFS(int i)

{

    for(int j=Head[i]; j!=-1; j=e[j].next)

    {

        int v = e[j].v;

        if( used[v] == false && dx[i] == dy[v]-1 )

        {

            used[v] = true;///开始忘记置为访问过错了一次

            if( My[v] && dy[v] == depth )

                continue;

            if( !My[v] || DFS(My[v]))

            {

                My[v] = i;

                Mx[i] = v;

                return true;

            }

        }

    }

    return false;

}

int  Karp()

{

    int ans = 0;

    while( BFS() == true )

    {

        memset(used, false, sizeof(used));

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

        {

            if( !Mx[i] && DFS(i) )

                ans++;

        }

    }

    ///因为点同时在两边，所以会重复一次，结果应该出去 2

    return ans / 2;

}

int main()

{

    int i, j, T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d%d", &M, &N);

        int sum = 0;///记录 ‘*’个数

        InIt();

        for(i=0; i<M; i++)

        {

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

            for(j=0; j<N; j++)

            {

                if(G[i][j] == '*')

                {///购置关系图

                    Index[i][j] = ++NX;///给点编号

                    sum++;

                    if(j != 0 && G[i][j-1] == '*')

                    {///与左边的可以匹配

                        AddEdge(Index[i][j], Index[i][j-1]);

                        AddEdge(Index[i][j-1], Index[i][j]);

                    }

                    if(i != 0 && G[i-1][j] == '*')

                    {///与上面的可以匹配

                        AddEdge(Index[i][j], Index[i-1][j]);

                        AddEdge(Index[i-1][j], Index[i][j]);;

                    }

                }

            }

        }

        int ans = Karp();

        printf("%d\n", sum-ans);

    }

    return 0; }