有墙的最大匹配问题
将行和列进行初始化划分 再对左图(r)右图(c)进行匈牙利算法
#include<bits/stdc++.h> using namespace std; #define N 105 char mp[N][N]; int mp2[N][N]; int used[N]; int vis[N]; int n,m,r,c; bool dfs(int x) { for(int j=1;j<=c;j++) { if(mp2[x][j]&&!used[j]) { used[j]=1; if(!vis[j]||dfs(vis[j])) { vis[j]=x; return true; } } } return false; } int find1(void) { int ans=0; memset(vis,0,sizeof(vis)); for(int i=1;i<=r;i++) { memset(used,0,sizeof(used)); if(dfs(i))ans++; } return ans; } int main() { while(scanf("%d",&n),n) { r=0,c=0; int hang[N][N]; int lie[N][N]; memset(hang,0,sizeof(hang)); memset(lie,0,sizeof(lie)); for(int i=1;i<=n;i++) scanf("%s",mp[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(mp[i][j]=='.') { if(j-1==0||mp[i][j-1]=='X') r++; hang[i][j] = r; } for(int j=1;j<=n;j++) for(int i=1;i<=n;i++) if(mp[i][j]=='.') { if(i-1==0||mp[i-1][j]=='X') c++; lie[i][j] = c; } memset(mp2,0,sizeof(mp2)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp2[ hang[i][j] ][ lie[i][j] ]=1; printf("%d\n",find1()); } }