题目大意：

一个矩形中，有N个城市’*’，现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。
问至少放置多少个基站才能使得所有的城市都覆盖无线？

无向二分图的最小路径覆盖 = 顶点数 ? 最大二分匹配数/2

路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int maxn = 500 + 5; struct BPM { int n, m; vector
      
        G[maxn]; int link[maxn]; bool vis[maxn]; void init(int n) { for(int i=0; i<=n+10; ++i) G[i].clear(); } void AddEdge(int u, int v) { G[u].push_back(v); } bool match(int u) { for(int i=0; i
       
        n = n; memset(link, -1, sizeof link ); int ans = 0; for(int u=1; u<=n; ++u) { memset(vis, 0, sizeof vis ); if(match(u)) ans++; } return ans; } }; BPM solver; int mtx[maxn][maxn]; int dir[4][2]={{-1,0}, {1,0}, {0,1}, {0,-1} }; int main() { int t, h, w; scanf("%d", &t); while(t--) { scanf("%d%d", &h, &w); solver.init(h*w); memset(mtx, 0, sizeof mtx ); int i, j; char str[maxn]; int cnt = 0; for(i=1; i<=h; ++i) { scanf("%s", str); for(j=0; j