这题我是在总结过程中想找二分匹配做做的，如果是平时我估计就直接深搜了。。
二分匹配一开始没想出来如何建图，开始的思路有点阻塞，后来突然就明白了。
题意，给一个n*n的棋盘 图中有X和。其中X代表墙，问棋盘中最多能放多少个‘车’使每个车都安全。
先对行搜索，一行中若隔一个X则相当于有2行，找出所有的行并标上序号，然后对列同样进行操作。这样二分图的两边的点就全找出来了。
然后对于图中每一个‘。’号进行连边将L【i】【j】与R【i】【j】相连，求最大匹配即是答案。
代码：
#include<iostream>
#include<cstring>
const int MAXN = 100;
using namespace std;
struct g{
int num;
int boy[MAXN];
}gr[MAXN];
bool flag[MAXN];
int pre[MAXN];
int n,m;
int DFS(int x)
{
for(int i=0;i<gr[x].num;i++) //男生
{
if(!flag[gr[x].boy[i]]) //未被匹配
{
flag[gr[x].boy[i]]=true;
if(pre[gr[x].boy[i]]==-1||DFS(pre[gr[x].boy[i]]))
{
pre[gr[x].boy[i]]=x; //第几个女生
return 1;
}
}
}
return 0;
}
char c[5][5];
int r[5][5];
int l[5][5];
int main()
{
int sum,k,a,b;
while(cin>>n&&n!=0)
{
for(int i=0;i<n;i++)
{
cin>>c[i];
}
//找行 标号
int temp=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(c[i][j]=='X')
{temp++;r[i][j]=-1;}
else
r[i][j]=temp;
if(j==n-1)temp++;
}
}
int rn=temp-1;
//找列
temp=1;
for(int j=0;j<n;j++)
{
for(int i=0;i<n;i++)
{
if(c[i][j]=='X')
{
temp++;l[i][j]=-1;
}
else
l[i][j]=temp;
if(i==n-1)temp++;
}
}
int ln=temp-1;
for(int i=0;i<=10;i++)
gr[i].num=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(l[i][j]!=-1)
{
gr[r[i][j]].boy[gr[r[i][j]].num++]=l[i][j];
}
}
sum=0;
memset(pre,-1,sizeof(pre));
for(int i=1;i<=rn;i++) //行
{
memset(flag,0,sizeof(flag));
sum+=DFS(i);
}
cout<<sum<<endl;
}
return 0;
}