hdu_1045 Fire Net 二分图匹配

时间:2021-06-25 06:14:25
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define N 10
char a[N][N];
int cnt1,cnt2;
int hash1[N][N];
int hash2[N][N];
bool edge[N][N];
int linker[N*N];
bool vis[N*N];

bool dfs(int u){
for(int i=0;i<cnt2;i++){
if(!vis[i]&&edge[u][i]){
vis[i]=1;
if(linker[i]==-1||dfs(linker[i])){
linker[i]=u;
return true;
}
}
}
return false;
}
int hungary(){
memset(linker,-1,sizeof(linker));
int ans=0;
for(int i=0;i<cnt1;i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) ans++;
}
return ans;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF&&n){
for(int i=0;i<n;i++){
scanf("%s",a[i]);
}
memset(hash1,-1,sizeof(hash1));
memset(hash2,-1,sizeof(hash2));
cnt1=0,cnt2=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='X') continue;
hash1[i][j]=cnt1;
if(j==n-1||a[i][j+1]=='X') cnt1++;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[j][i]=='X') continue;
hash2[j][i]=cnt2;
if(j==n-1||a[j+1][i]=='X') cnt2++;
}
}
memset(edge,0,sizeof(edge));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(a[i][j]=='X') continue;
edge[hash1[i][j]][hash2[i][j]]=1;
}
}
printf("%d\n",hungary());
}
return 0;
}