1 /*两个代码：一个是输入建图匹配的时候上下左右寻找。一个是先利用*的上下左右建图。*/  2 #include <algorithm>  3 #include <iostream>  4 #include <sstream>  5 #include <cstdlib>  6 #include <cstring>  7 #include <cstdio>  8 #include <string>  9 #include <bitset> 10 #include <vector> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <list> 15 //#include <map> 16 #include <set> 17 using namespace std; 18 /***************************************/ 19 #define ll long long 20 #define int64 __int64 21 /***************************************/ 22 const int INF = 0x7f7f7f7f; 23 const double eps = 1e-8; 24 const double PIE=acos(-1.0); 25 const int d1x[]= {-1,1,0,0}; 26 const int d1y[]= {0,0,-1,1}; 27 const int d2x[]= {0,-1,0,1}; 28 const int d2y[]= {1,0,-1,0}; 29 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 30 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 31 /***************************************/ 32 void openfile() 33 { 34     freopen("data.in","rb",stdin); 35     freopen("data.out","wb",stdout); 36 } 37 /**********************华丽丽的分割线,以上为模板部分*****************/ 38 #define MAXN 505 39 int nx,ny; 40 int G[MAXN][MAXN]; 41 int cx[MAXN][MAXN],cy[MAXN][MAXN]; 42 int vis[MAXN][MAXN]; 43 int path(int x1,int y1) 44 { 45     int i; 46     int x,y; 47     for(i=0; i<4; i++) 48     { 49         x=x1+d1x[i]; 50         y=y1+d1y[i]; 51         if (G[x][y]&&!vis[x][y]) 52         { 53             vis[x][y]=-1; 54             if (cy[x][y]==-1||path(cx[x][y],cy[x][y])) 55             { 56                 cx[x][y]=x1; 57                 cy[x][y]=y1; 58                 return 1; 59             } 60         } 61     } 62     return 0; 63 } 64 int MaxMatch() 65 { 66     int cnt=0; 67     memset(cx,-1,sizeof(cx)); 68     memset(cy,-1,sizeof(cy)); 69     int i,j; 70     for(i=0; i<nx; i++) 71         for(j=0; j<ny; j++) 72         { 73             memset(vis,0,sizeof(vis)); 74             if (G[i][j]==1) 75                 cnt+=path(i,j); 76         } 77     return cnt; 78 } 79 int main() 80 { 81     int cas; 82     scanf("%d",&cas); 83     while(cas--) 84     { 85         //  int m; 86         scanf("%d%d",&nx,&ny); 87         int i,j; 88         int x,y; 89         int min=0; 90         int sum=0; 91         char c; 92         memset(G,0,sizeof(G)); 93         getchar(); 94         for(i=0; i<nx; i++) 95         { 96             for(j=0; j<ny; j++) 97             { 98                 scanf("%c",&c); 99                 if (c==‘*‘)100                 {101                     G[i][j]=1;102                     sum++;103                 }104             }105             getchar();106         }107         min+=MaxMatch();108         min=sum-min/2;109         printf("%d\n",min);110     }111     return 0;112 }113 /*********************************************/114 #include <algorithm>115 #include <iostream>116 #include <sstream>117 #include <cstdlib>118 #include <cstring>119 #include <cstdio>120 #include <string>121 #include <bitset>122 #include <vector>123 #include <queue>124 #include <stack>125 #include <cmath>126 #include <list>127 #include <map>128 #include <set>129 using namespace std;130 /***************************************/131 typedef vector<int> VI;132 typedef vector<char> VC;133 typedef vector<string> VS;134 typedef set<int> SI;135 typedef set<string> SS;136 typedef map<int ,int> MII;137 typedef map<string,int> MSI;138 typedef pair<int,int> PII;139 typedef vector<PII> VII;140 typedef vector<VI > VVI;141 /***************************************/142 #define clr(a,b) memset(a,b,sizeof(a))143 #define all(x)    (x).begin(), (x).end()144 #define sz(x) ((int)(x).size())145 #define ll long long146 #define int64 __int64147 #define pb push_back148 #define mp make_pair149 #define LL(x) ((x)<<1)150 #define RR(x) ((x)<<1|1)151 #define ri(x) scanf("%d",&x)152 #define rii(x,y) scanf("%d%d",&x,&y)153 #define rd(x) scanf("%lf",&x)154 #define rdd(x,y) scanf("%lf%lf",&x,&y)155 #define rs(x) scanf("%s",x)156 #define pi(x) printf("%d",x)157 #define pin(x) printf("%d\n",x)158 #define ps(x) printf("%s",x)159 #define pn()  printf("\n")160 #define sqr(x) ((x)*(x))161 #define rep(i,a,b)  for(int i=(a);i<(b);i++)162 #define repu(i,a,b) for(int i=(a);i<=(b);i++)163 #define repd(i,a,b) for(int i=(a);i>=(b);i--)164 #define repc(i,a,c) for(int i=(a);(c);i++)165 /***************************************/166 const int INF = 0x7f7f7f7f;167 const double eps = 1e-8;168 const double PIE=acos(-1.0);169 const int dx[]= {0,1,0,-1};170 const int dy[]= {1,0,-1,0};171 const int fx[]= {-1,-1,-1,0,0,1,1,1};172 const int fy[]= {-1,0,1,-1,1,-1,0,1};173 /***************************************/174 void openfile()175 {176     freopen("data.in","rb",stdin);177     freopen("data.out","wb",stdout);178 }179 /**********************The End OF The Template*****************/180 181 const int N = 410;182 char edge[45][15];183 int h,w;184 vector<int>graph[N];185 int mx[N],my[N],vis[N];186 187 void init()188 {189     rep(i,0,N)190         graph[i].clear();191     clr(mx,-1);192     clr(my,-1);193 }194 195 int dfs(int u)196 {197     rep(i,0,(int)graph[u].size())198     {199         int v=graph[u][i];200         if(!vis[v])201         {202             vis[v]=1;203             if(my[v]==-1||dfs(my[v]))204             {205                 my[v]=u;206                 mx[u]=v;207                 return 1;208             }209         }210     }211     return 0;212 }213 214 int hungray()215 {216     int cnt=0;217     rep(i,0,w*h)218     {219         if(mx[i]==-1)220         {221             clr(vis,0);222             if(dfs(i)) cnt++;223         }224     }225     return cnt;226 }227 228 int main()229 {230     int T;231     ri(T);232     while(T--)233     {234         init();235         rii(h,w);236         rep(i,0,h)237             rs(edge[i]);238         int ans=0;239         rep(i,0,h)240         {241             rep(j,0,w)242             {243                 if(edge[i][j]==‘*‘)244                 {245                     ans++;246                     int x=i*w+j;247                     rep(k,0,4)248                     {249                         int newx=i+dx[k];250                         int newy=j+dy[k];251                         if(newx>=0&&newx<h&&newy>=0&&newy<w&&edge[newx][newy]==‘*‘)252                         {253                             int y=newx*w+newy;254                             graph[x].push_back(y);255                         }256                     }257                 }258             }259         }260         //pin(hungray()/2);261         printf("%d\n",ans-hungray()/2);262     }263     return 0;264 }