这题也可以用搜索来做
但用匹配做更简单
//Time 0ms,Memory 332K
#include<iostream>
#include<cstring>
using namespace std;
char city[4][5];
int n,l1,l2,vis[10],flag[10],p[4][4],q[4][4],pq[10][10];
int f(int u)
{
int i;
for(i=0;i<l1;i++) if(!vis[i] && pq[i][u])
{
vis[i]=1;
if(flag[i]==-1 || f(flag[i]))
{
flag[i]=u;return 1;
}
vis[i]=0;
}
return 0;
}
int main()
{
int i,j,t;
while(cin>>n && n)
{
l1=0;t=0;
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
memset(pq,0,sizeof(pq));
memset(flag,-1,sizeof(flag));
for(i=0;i<n;i++)
cin>>city[i];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(city[i][j]!='.')
{
if(t)
{
l1++;t=0;
}
}
else
{
p[i][j]=l1;t=1;
}
}
if(t)
{
l1++;t=0;
}
}
if(t) l1++;
l2=0;t=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(city[j][i]!='.')
{
if(t)
{
l2++;t=0;
}
}
else
{
q[j][i]=l2;t=1;
}
}
if(t)
{
l2++;t=0;
}
}
if(t) l2++;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++) if(city[i][j]=='.')
{
pq[p[i][j]][q[i][j]]=1;
}
}
int cnt=0;
for(i=0;i<l2;i++)
{
memset(vis,0,sizeof(vis));
if(f(i)) cnt++;
}
cout<<cnt<<endl;
}
return 0;
}