题意就不说了，求二部图最大匹配。
问题是怎么建图……
给定的条件中，h<40,w<10,所以笔者直接默认所有情况的地图都是40*10，当然，超出范围的便是空城o。
然后给城市编号。一个城市只能和上下左右4个城市公用天线。换个换说就像国际象棋的棋盘一样，黑色格子与白色格子自然分成了二部图。黑色只能和白色匹配。
编号也很简单了。从第一行开始，第一格是黑色城市1，然后白色城市1，然后黑色城市2，白色城市2……因为所有的图都默认一样大小，所以编号可以重用。
为了方便知道（i,j）到底是黑色还是白色，我们可以用正数编号表示黑色，负数编号表示白色。
然后求最大匹配，直接匈牙利过去就好了。
贴代码，0MS
#include <cstdio>
#include <cstring> const int maxn=;
bool mp[maxn][maxn];
bool vis[maxn];
int link[maxn];
int No[][];
int n; bool DFS(int x)
{
for(int y=;y<=n;y++)
{
if(mp[x][y] && !vis[y])
{
vis[y]=true;
if(link[y]== || DFS(link[y]))
{
link[y]=x;
return true;
}
}
}
return false;
} int maxMartch()
{
int count=;
for(int x=;x<=n;x++)
{
memset(vis,,sizeof(vis));
if(DFS(x))
count++;
}
return count;
} int main()
{
int T;
scanf("%d",&T); int index=;
for(int i=;i<;i++)
for(int j=;j<;j++,index++)
No[i][j]=(index/)*((index+i)%?-:);
n=; while(T--)
{
int num=;
int w,h;
scanf("%d%d",&h,&w);
if(w%)
w++; char str[][];
memset(mp,,sizeof(mp));
memset(link,,sizeof(link));
memset(str,,sizeof(str));
for(int i=;i<h;i++)
{
scanf("%s",str[i&]);
if(str[i&][]=='*')
{
num++;
if(str[-i&][]=='*')
{
if(No[i][]>)
mp[No[i][]][-No[i-][]]=true;
else
mp[No[i-][]][-No[i][]]=true;
}
}
for(int j=; j<w; j++)
{
if(str[i&][j]=='*')
{
num++;
if(str[i&][j-]=='*')
{
if(No[i][j]>)
mp[No[i][j]][-No[i][j-]]=true;
else
mp[No[i][j-]][-No[i][j]]=true;
} if(str[-i&][j]=='*')
{
if(No[i][j]>)
mp[No[i][j]][-No[i-][j]]=true;
else
mp[No[i-][j]][-No[i][j]]=true;
}
}
}
}
printf("%d\n",num-maxMartch());
}
}
整个建图是自己想的，好像略似繁琐……不过还好，比赛的时候估计也能这么想到吧。