题意：图没什么用 给出一个地图 地图上有 点 一次可以覆盖2个连续 的点（ 左右 或者 上下表示连续）问最少几条边可以使得每个点都被覆盖
最小路径覆盖 最小路径覆盖=|G|-最大匹配数 证明：https://blog.****.net/qq_34564984/article/details/52778763
证明总的来说就是尽可能多得连边 边越多 可以打包一起处理得点就越多（这里题中打包指连续得两个点只需要一条线段就能覆盖）
拆点思想 ：匈牙利拆了点才好写 不然十分麻烦 简单地说就是点复制一遍 从一边开始匹配
建图：X如果需要覆盖 和它上下左右需要覆盖的点连边 当然这里是和拆完点的另外一个部分的点连边 amp[x][y]两维 分别表示两个集合
答案 最小路径覆盖 = 顶点数 – 最大二分匹配数/2 为什么要除以2呢，因为拆点复制了一遍 需要除回去 比如
1 2 有变 变成
1 和2'
2 和 1'形成了匹配 这样匹配就加倍了 所以除以2就好
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=;
char mp[maxn][maxn];
int amp[maxn][maxn];
int vis[maxn];
int Hash[maxn][maxn];
int cnt=;
int ans=;
int link[maxn];
int dx[]={
,-,,
};
int dy[]={
,,-,
};
bool dfs(int x){
for(int i=;i<=cnt;i++){
if(amp[x][i]&&!vis[i]){
vis[i]=;
if(link[i]==||dfs(link[i])){
link[i]=x;
return ;
}
}
}
return ;
}
void solve(){
ans=;
memset(link,,sizeof(link));
for(int i=;i<=cnt;i++){
memset(vis,,sizeof(vis));
if(dfs(i))ans++;
}
}
int main(){
int t; cin>>t;
while(t--){
int n,m;
cnt=;
memset(amp,,sizeof(amp));
cin>>n>>m;
for(int i=;i<=n;i++)scanf("%s",mp[i]+);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]=='*') Hash[i][j]=++cnt;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]=='*'){
for(int k=;k<;k++){
int tx=i+dx[k],ty=j+dy[k];
if(mp[tx][ty]=='*')amp[Hash[i][j]][Hash[tx][ty]]=;
}
}
}
}
solve();
cout<<cnt-ans/<<endl;
} return ;
}