题意分析

题目要求在一个矩阵中放置尽可能少的天线，使得所有兴趣点（*）被覆盖。每个天线放置在位置 $(r, c)$ 时，可以覆盖自身及一个相邻方向（上下左右之一）的位置。因此，每个天线最多覆盖两个兴趣点（自身和相邻点）。问题转化为如何用最少的天线覆盖所有兴趣点，等价于寻找最少的点对，使得每个点对中的两个点相邻，且所有点被覆盖或单独被覆盖。

解题思路

1. 模型转换：
   将每个兴趣点视为图中的节点，若两个兴趣点相邻（上下左右），则在它们之间连一条边。问题转化为在这个图中找到最少的边数，使得所有节点被边覆盖或单独存在。最少边数对应的天线数为：总节点数 - 最大匹配数，因为每条边对应一个天线覆盖两个节点，剩余节点各需一个天线。

2. 二分图匹配：
   构建兴趣点之间的相邻关系图，利用匈牙利算法求解最大匹配。最大匹配数表示可以通过一条天线覆盖两个节点的最大对数。最终答案为总节点数减去最大匹配数（每条匹配边减少一个天线）。

代码解释

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 440;  // 最大节点数（40行×10列=400，预留余量）

bool Map[MAXN][MAXN];  // 邻接矩阵，表示节点间的相邻关系
bool Mask[MAXN];       // 匹配过程中的访问标记
int NX, NY;            // 二分图的左右两部分节点数（此处为同一集合）
int cx[MAXN], cy[MAXN]; // 匹配数组，记录左右节点的匹配对象

// 四个方向：右、左、下、上
int DireR[4] = {0, 0, 1, -1};
int DireC[4] = {1, -1, 0, 0};
int iMap[MAXN][MAXN];  // 兴趣点编号矩阵
char G[44][11];        // 输入矩阵

// 匈牙利算法寻找增广路径
int FindPath(int u) {
    for (int i = 1; i <= NY; ++i) {
        if (Map[u][i] && !Mask[i]) {  // 存在边且未访问过
            Mask[i] = 1;
            // 递归寻找增广路径
            if (cy[i] == -1 || FindPath(cy[i])) {
                cy[i] = u;
                cx[u] = i;
                return 1;
            }
        }
    }
    return 0;
}

// 计算最大匹配数
int MaxMatch() {
    memset(cx, -1, sizeof(cx));
    memset(cy, -1, sizeof(cy));
    int res = 0;
    for (int i = 1; i <= NX; ++i) {
        if (cx[i] == -1) {  // 未匹配的节点
            memset(Mask, 0, sizeof(Mask));
            res += FindPath(i);
        }
    }
    return res;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int N, M, id = 1;
        scanf("%d%d", &N, &M);
        memset(iMap, 0, sizeof(iMap));
        // 读取矩阵并为兴趣点编号
        for (int i = 1; i <= N; ++i) {
            getchar();  // 处理换行符
            for (int j = 1; j <= M; ++j) {
                scanf("%c", &G[i][j]);
                if (G[i][j] == '*')
                    iMap[i][j] = id++;  // 分配唯一编号
            }
        }
        // 构建邻接矩阵：相邻兴趣点之间连边
        memset(Map, 0, sizeof(Map));
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= M; ++j) {
                if (iMap[i][j]) {  // 当前位置是兴趣点
                    int u = iMap[i][j];
                    for (int k = 0; k < 4; ++k) {  // 检查四个方向
                        int x = i + DireR[k];
                        int y = j + DireC[k];
                        if (iMap[x][y]) {  // 相邻位置也是兴趣点
                            int v = iMap[x][y];
                            Map[u][v] = true;  // 无向图，邻接矩阵对称
                        }
                    }
                }
            }
        }
        NX = NY = id - 1;  // 总节点数为id-1
        int max_match = MaxMatch()/2;
        // 最少天线数 = 总节点数 - 最大匹配数（每条匹配边减少一个天线）
        printf("%d\n", (id - 1) - max_match);
    }
    return 0;
}

关键步骤解析

1. 兴趣点编号：
   遍历矩阵，为每个兴趣点（*）分配唯一编号$id$，便于构建图的节点。设总节点数为$V = id - 1$。

2. 邻接矩阵构建：
   对每个兴趣点$(i, j)$，检查其四个相邻方向$(i+dr[k], j+dc[k])$。若相邻位置也是兴趣点，即在对应的节点$u = iMap[i][j]$和$v = iMap[x][y]$之间连边$Map[u][v] = \text{true}$。

3. 最大匹配计算：
   使用匈牙利算法求解二分图的最大匹配。这里将图视为自环的二分图（左部和右部均为所有节点），通过邻接矩阵表示无向边。最大匹配数(max_match)表示可以通过一条天线覆盖两个节点的最大对数。

4. 结果计算：
   每个匹配边对应一个天线覆盖两个节点，因此最少天线数为总节点数减去最大匹配数，即：
   $\text{最少天线数} = V - max\_match$
   其中，$V$为兴趣点总数，$max\_match$为最大匹配数。

复杂度分析

• 时间复杂度：$O(T \times V \times E)$，其中 $T$ 为测试用例数，$V$ 为兴趣点数量，$E$ 为边数。对于 $h=40$，$w=10$，最多 $V=400$ 个节点，$E \approx 4V$，单个测试用例的时间复杂度为 $O(400 \times 1600) = 6.4 \times 10^5$，可接受。

• 空间复杂度：$O(V^2)$，邻接矩阵存储需要 $O(V^2)$ 空间，对于 $V=400$，占用约$160000$ 字节，符合内存限制。

总结

通过将问题转化为图的最大匹配问题，利用匈牙利算法高效求解，能够在合理时间内找到覆盖所有兴趣点的最少天线数。该方法巧妙地将相邻覆盖关系建模为图的边，通过匹配减少天线使用量，是组合优化问题的典型应用。