<题目链接>
题目大意：
这题意思是给出一张图，图中'X'表示wall,'.'表示空地,可以放置炮台，同一条直线上只能有一个炮台，除非有'X'隔开，问在给出的图中最多能放置多少个炮台。
解题分析：
本题可用DFS求解 >>> ，但是二分匹配的想法更加巧妙，效率也更高。二分匹配的主要思想就是，对矩阵的行连通块和列连通块进行标号，然后根据矩阵的每个点，建立对应的行连通块和列连通块之间的待匹配关系，然后利用匈牙利进行正式匹配，这样当某个行联通块与某个列连通块正式确立匹配关系的时候，说明这两个连通块的交点坐标(之一)放碉堡，而它们的其它部分则不能放碉堡。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int nrow,ncol;
int g[][],linker[];
bool used[];
char map[][];
int maprow[][],mapcol[][];
bool dfs(int u){
for(int v=;v<=ncol;v++)
if(g[u][v]&&!used[v]){
used[v]=true;
if(!linker[v]||dfs(linker[v])){
linker[v]=u;
return true;
}
}
return false;
}
int Hungary(){
int res=;
memset(linker,,sizeof(linker)); //将行连通块的归属全部置为空
for(int u=;u<=nrow;u++){
memset(used,,sizeof(used));
if(dfs(u))res++;
}
return res;
}
int main(){
int i,j,n;
while(scanf("%d",&n),n){
memset(mapcol,,sizeof(mapcol));
memset(maprow,,sizeof(maprow));
memset(g,,sizeof(g));
for(i=;i<=n;i++){
for(j=;j<=n;j++){
cin>>map[i][j];
if(map[i][j]=='X')
mapcol[i][j]=maprow[i][j]=-; //X点的行连通编号和列连通编号均标为-1
}
}
int p1=;
nrow=;ncol=;
//给行编号
for(i=;i<=n;i++){
for(j=;j<=n;j++){
while(maprow[i][j]==-&&j<=n) //跳过这一行的X部分
j++;
p1++; //p1代表序号
while(maprow[i][j]!=-&&j<=n){
maprow[i][j]=p1; //给第i行连续的连通块打上相同标号p1
if(nrow<p1) nrow=p1; //记录所有行中，行联通块的最大编号
j++;
}
}
}
int p2=;
//给列编号
for(j=;j<=n;j++)
for(i=;i<=n;i++){
while(mapcol[i][j]==-&&i<=n) //遍历第j列的时候，跳过X部分
i++;
p2++;
while(mapcol[i][j]!=-&&i<=n){
mapcol[i][j]=p2; //给第j列的连续的联通块标上相同的序号
if(ncol<p2)ncol=p2; //记录下所有列中，列连通块的最大标号
i++;
}
}
for(i=;i<=n;i++)
for(j=;j<=n;j++){
if(maprow[i][j]!=-&&mapcol[i][j]!=-)
g[maprow[i][j]][mapcol[i][j]]=; //将每个空格点的行连通标号与列连通标号 构建匹配关系
}
printf("%d\n",Hungary());
}
return ;
}
2018-11-10