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