给你一个平面图上，图上有城市和空地，城市用 * 表示，空地用 o 表示，让你建设最少数量的基站来覆盖所有城市．一个基站可以覆盖上下相邻，或者左右相邻的两个城市．求建设基站的数量．

二分图的最小路径覆盖问题．将相邻的两个城市间连一条边，那么所要求的就是至少有多少条边，能够把所有城市都覆盖．（如果一个城市周围都没有其它城市，那不就是没有边跟它相连？）

拿组简单的数据分析下：

oooo
*o*o
o**o

对于上面这组数据的城市，给它标号为：

oooo
1o2o
o34o

拆点，建立如下的二分图（没把边画出来）：
1 1′

2 2′

3 3′

4 4′
其中，2 跟 4′ 相连， 3跟 4’相连，4跟2’相连，4跟3’相连．

可以根据图中易得匹配数（记为 k）为２（2->4’，4->2’），匹配数 / 2 = 基站数量，就是说用了一条边（基站）匹配了两个城市，总共有 cnt 个城市，剩下还有 cnt – k 个城市，这剩下的城市就得自己建设一个基站给自己，剩下的城市总共建设了 cnt – k 个基站，所以最终答案总共建设了 cnt - k + k / 2个基站．（最小路径覆盖问题）

要注意区分最小路径覆盖跟最小点覆盖．

最小路径覆盖：用最少的边覆盖所有的点．其结果等于（顶点数－二分图最大匹配数／２）．

最小点覆盖：用最少的点覆盖所有边．

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>

using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
int w, h;
char mp[50][50];
int rec[50][50];
vector<int> G[405];
int vis[405];
int match[405];
bool dfs(int u)
{
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (vis[v])
            continue;
        vis[v] = 1;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &h, &w);
        int cnt = 0;
        for (int i = 0; i < h; i++) {
            scanf("%s", mp[i]);
            for (int j = 0; j < w; j++) {
                if (mp[i][j] == '*')
                    rec[i][j] = cnt++;
            }
        }
        for (int i = 0; i <= cnt; i++)
            G[i].clear();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (mp[i][j] == '*') {
                    for (int k = 0; k < 4; k++) {
                        int nx = dx[k] + i, ny = dy[k] + j;
                        if (0 <= nx && nx < h && 0 <= ny && ny < w && mp[nx][ny] == '*') {
                            int u = rec[i][j], v = rec[nx][ny];
                            G[u].push_back(v);
                        }
                    }
                }
            }
        }
        int tmp = 0;
        memset(match, -1, sizeof(match));
        for (int i = 0; i < cnt; i++) {
            memset(vis, 0, sizeof(vis));
            tmp += dfs(i);
        }
        printf("%d\n", cnt - tmp / 2);
    }
    return 0;
}