<题目链接>
题目大意：
这题意思是给出一张图，图中'X'表示wall,'.'表示空地,可以放置炮台，同一条直线上只能有一个炮台，除非有'X'隔开，问在给出的图中最多能放置多少个炮台。
解题分析：
本题可用DFS求解 >>> ，但是二分匹配的想法更加巧妙，效率也更高。二分匹配的主要思想就是，对矩阵的行连通块和列连通块进行标号，然后根据矩阵的每个点，建立对应的行连通块和列连通块之间的待匹配关系，然后利用匈牙利进行正式匹配，这样当某个行联通块与某个列连通块正式确立匹配关系的时候，说明这两个连通块的交点坐标(之一)放碉堡，而它们的其它部分则不能放碉堡。
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 int nrow,ncol; 7 int g[20][20],linker[20]; 8 bool used[20]; 9 char map[5][5]; 10 int maprow[5][5],mapcol[5][5]; 11 bool dfs(int u){ 12 for(int v=1;v<=ncol;v++) 13 if(g[u][v]&&!used[v]){ 14 used[v]=true; 15 if(!linker[v]||dfs(linker[v])){ 16 linker[v]=u; 17 return true; 18 } 19 } 20 return false; 21 } 22 int Hungary(){ 23 int res=0; 24 memset(linker,0,sizeof(linker)); //将行连通块的归属全部置为空 25 for(int u=1;u<=nrow;u++){ 26 memset(used,0,sizeof(used)); 27 if(dfs(u))res++; 28 } 29 return res; 30 } 31 int main(){ 32 int i,j,n; 33 while(scanf("%d",&n),n){ 34 memset(mapcol,0,sizeof(mapcol)); 35 memset(maprow,0,sizeof(maprow)); 36 memset(g,0,sizeof(g)); 37 for(i=1;i<=n;i++){ 38 for(j=1;j<=n;j++){ 39 cin>>map[i][j]; 40 if(map[i][j]=='X') 41 mapcol[i][j]=maprow[i][j]=-1; //X点的行连通编号和列连通编号均标为-1 42 } 43 } 44 int p1=0; 45 nrow=0;ncol=0; 46 //给行编号 47 for(i=1;i<=n;i++){ 48 for(j=1;j<=n;j++){ 49 while(maprow[i][j]==-1&&j<=n) //跳过这一行的X部分 50 j++; 51 p1++; //p1代表序号 52 while(maprow[i][j]!=-1&&j<=n){ 53 maprow[i][j]=p1; //给第i行连续的连通块打上相同标号p1 54 if(nrow<p1) nrow=p1; //记录所有行中，行联通块的最大编号 55 j++; 56 } 57 } 58 } 59 int p2=0; 60 //给列编号 61 for(j=1;j<=n;j++) 62 for(i=1;i<=n;i++){ 63 while(mapcol[i][j]==-1&&i<=n) //遍历第j列的时候，跳过X部分 64 i++; 65 p2++; 66 while(mapcol[i][j]!=-1&&i<=n){ 67 mapcol[i][j]=p2; //给第j列的连续的联通块标上相同的序号 68 if(ncol<p2)ncol=p2; //记录下所有列中，列连通块的最大标号 69 i++; 70 } 71 } 72 for(i=1;i<=n;i++) 73 for(j=1;j<=n;j++){ 74 if(maprow[i][j]!=-1&&mapcol[i][j]!=-1) 75 g[maprow[i][j]][mapcol[i][j]]=1; //将每个空格点的行连通标号与列连通标号 构建匹配关系 76 } 77 printf("%d ",Hungary()); 78 } 79 return 0; 80 }
2018-11-10