http://poj.org/problem?id=3020
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000
using namespace std;
int t,n,m;
char g[maxn][maxn];
int map1[maxn][maxn];
int gg[maxn][maxn];
bool vis[maxn];
int match[maxn];
int dir[][]={{,-},{,},{,},{-,}};
int res,num;
int dfs(int p)
{
int i,t;
for(i=; i<=num; i++)
{
if(gg[i][p]&&!vis[i])
{
vis[i]=true;
t=match[i];
match[i]=p;
if(t==-||dfs(t))
return ;
match[i]=t;
}
}
return ;
}
void pro()
{
int i;res=;
for(i=; i<=num; i++)
{
memset(vis,false,sizeof(vis));
res+=dfs(i);
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
memset(match,-,sizeof(match));
memset(gg,,sizeof(gg));
memset(map1,,sizeof(map1));
num=;
scanf("%d%d",&n,&m);
for(int i=; i<n; i++)
{
scanf("%s",g[i]);
for(int j=; j<m; j++)
{
if(g[i][j]=='*')
{
map1[i][j]=++num;
}
}
}
for(int i=; i<n; i++)
{
for(int j=; j<m; j++)
{
if(map1[i][j])
{
for(int k=; k<; k++)
{
int x=i+dir[k][];
int y=j+dir[k][];
if(map1[x][y])
{
gg[map1[i][j]][map1[x][y]]=;
}
}
}
}
}
pro();
printf("%d\n",num-res/);
}
return ;
}