思路：
二分匹配难点就在于建图，怎样有效的建立好模型，决定这个题的成败
方法一：此题数据范围较小，可以搜索（DFS）
方法二：以“方格块”建图，每个横向的连续空地作为一个X集的结点，每个纵向的连续空地作为一个Y集的结点
以题目的第一个例子作说明：
如下是所建的图：
如果两个方格块之间有公共点，就在两者之间连一条边。上面例子得到的二分图如下：
— 于是，每条边对应棋盘上的一个格子。这个图的最大匹配即为最多可放的个数
最后的结果：
AC code （二分匹配）
#include<stdio.h>
#include<string.h>
char map[5][5];
int mapr[5][5],mapl[5][5];
int g[20][20];/*存储边的信息*/
int link[20],use[20];
int uN,vN;
int ans;
int dfs(int u)/*找增广路*/
{
int v;
for(v=1;v<=vN;v++)
if(g[u][v]==1&&use[v]==0)
{
use[v]=1;
if(link[v]==-1||dfs(link[v]))
{
link[v]=u;
return 1;
}
}
return 0;
}
int hungry()/*匈牙利算法*/
{
int res;
int u;
res=0;
memset(link,-1,sizeof(link));/*初始化为-1*/
for(u=1;u<=uN;u++)
{
memset(use,0,sizeof(use));
if(dfs(u))res++;
}
return res;
}
int main()
{
int n;
int i,j;
while(scanf("%d",&n)!=-1&&n)
{
getchar();
memset(mapr,0,sizeof(mapr));
memset(mapl,0,sizeof(mapl));
memset(g,0,sizeof(g));
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%c",&map[i][j]);
if(map[i][j]=='X')
mapr[i][j]=mapl[i][j]=-1;
}
getchar();
}
uN=0;/*对行的连续区域进行标记*/
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
while(mapr[i][j]==-1&&j<=n)
j++;
uN++;
while(mapr[i][j]!=-1&&j<=n)
{
mapr[i][j]=uN;
j++;
}
}
vN=0;/*对列的连续区域进行标记*/
for(j=1;j<=n;j++)
for(i=1;i<=n;i++)
{
while(mapl[i][j]==-1&&i<=n)
i++;
vN++;
while(mapl[i][j]!=-1&&i<=n)
{
mapl[i][j]=vN;
i++;
}
}
for(i=1;i<=n;i++)/*建图*/
for(j=1;j<=n;j++)
{
if(mapr[i][j]!=-1&&mapl[i][j]!=-1)
g[mapr[i][j]][mapl[i][j]]=1;
}
ans=hungry();
printf("%d\n",ans);
}
return 0;
}
AC code（DFS）
#include<stdio.h>
#include<string.h>
#define inf 0x3f3f3f3f
char map[5][5];
int max_num;
int n;
int check(int r,int c)/*判断是否可以放*/
{
int i;
for(i=r;i>=0;i--)
{
if(map[i][c]=='O')return 0;
if(map[i][c]=='X')break;
}
for(i=c;i>=0;i--)
{
if(map[r][i]=='O')return 0;
if(map[r][i]=='X')break;
}
return 1;
}
void dfs(int i,int num)
{
int r,c;
if(i==n*n)
{
if(num>max_num)
max_num=num;
return;
}
else
{
r=i/n;
c=i%n;
if(map[r][c]!='X'&&check(r,c))
{
map[r][c]='O';
dfs(i+1,num+1);
map[r][c]='.';/*复原*/
}
dfs(i+1,num);
}
}
int main()
{
int i;
while(scanf("%d",&n)!=-1&&n)
{
getchar();
memset(map,0,sizeof(map));
for(i=0;i<n;i++)
{
scanf("%s",map[i]);/*注意输入的格式*/
getchar();
}
max_num=-inf;
dfs(0,0);
printf("%d\n",max_num);
}
return 0;
}