题目链接：https://vjudge.net/problem/19334/origin
题目大意：
如图：每个车不能“碰面”（每行每列只能一个：出除非墙隔开）
问给你一个棋盘，最多能放多少个车？多样例。

输入
4
.X…
…
XX…
…

输出：
5

思路：把行与列做匹配，把每一行和每列进行编号。有墙就是新点。

#include <bits/stdc++.h>
using namespace std;

const int N=165;  // 最大点数
const int INF=1<<28;  // 距离初始值

int g[N][N];  //二分图
int Mx[N];  //Mx[i]表示左集合i顶点所匹配的右集合的顶点序号
int My[N];  //My[i]表示右集合i顶点所匹配的左集合的顶点序号
int dx[N];
int dy[N];
bool used[N];

int Nx,Ny,dis;


 //寻找 增广路径集
bool searchP()
{
    dis=INF;
    int i,v,u;
    std::queue<int> Q;

    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));
    for(i=1;i<=Nx;i++)
    {   //cx[i]表示左集合i顶点所匹配的右集合的顶点序号
        if(Mx[i]==-1)
        {
            //将未遍历的节点 入队 并初始化次节点距离为0
            Q.push(i);
            dx[i]=0;
        }
    }
    //广度搜索增广路径
    while(!Q.empty())
    {
        u=Q.front();
        Q.pop();
        if(dx[u]>dis) break;
        //取右侧节点
        for(v=1;v<=Ny;v++)
        {
            //右侧节点的增广路径的距离
            if(g[u][v]&&dy[v]==-1)
            {
                dy[v]=dx[u]+1;   //v对应的距离 为u对应距离加1
                if(My[v]==-1) dis=dy[v]; //如果该点未被匹配，那么增广路形成
                else                       //如果该点匹配了，那么接着往下搜
                {
                    dx[My[v]]=dy[v]+1;
                    Q.push(My[v]);
                }
            }
        }
    }
    return dis!=INF;
}

//寻找路径 深度搜索
bool DFS(int u)
{
    int v;
    for(v=1;v<=Ny;v++)
    {
        //如果该点没有被遍历过 并且距离为上一节点+1
        if(g[u][v]&&!used[v]&&dy[v]==dx[u]+1)
        {
            //对该点染色
            used[v]=true;
            if(My[v]!=-1&&dy[v]==dis) continue; //如果该点已经被匹配了并且为最后一个匹配点，那么这条路径不是增广路。即是说这条路的结点已经匹配
            if(My[v]==-1||DFS(My[v]))  //如果该点未匹配或者后面的点能腾出位置，那么这就是增广路
            {
                My[v]=u;
                Mx[u]=v;
                return true;
            }
        }
    }
    return false;
}

//得到最大匹配的数目
int Hungary()
{
    int u;
    int ret=0;
    memset(Mx,-1,sizeof(Mx));
    memset(My,-1,sizeof(My));
    while(searchP())  //如果存在增广路
    {
        memset(used,false,sizeof(used));
        for(u=1;u<=Nx;u++)
           if(Mx[u]==-1&&DFS(u))  ret++;
    }
    return ret;
}

char a[100][100];
int X[100][100], Y[100][100];
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        Nx=Ny=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%s",a[i]+1);
        }
        memset(g,0,sizeof(g));
        //Ny=Nx>Ny? Nx:Ny;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]=='.')
                {
                    if(j==1||a[i][j-1]=='X')
                    {
                        Nx++;
                    }
                    X[i][j]=Nx;
                }
                if(a[j][i]=='.')
                {
                    if(j==1||a[j-1][i]=='X')
                    {
                        Ny++;
                    }
                    Y[j][i]=Ny;
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(a[i][j]=='.')
                g[X[i][j]][Y[i][j]]=1;
            }
        }

        int ans=Hungary();
        printf("%d\n",ans);
    }
    return 0;
}