题目：Fire Net
总结：构图+二分图匹配（匈牙利算法）
#include <stdio.h> #include <vector> #include <string.h> using namespace std; const int N = 105; vector<int>G[N]; int n; char s[N][N]; int a[N][N],b[N][N],vis[N],pre[N]; void init(){ memset(pre,0,sizeof pre); memset(a,0,sizeof a); memset(b,0,sizeof b); for(int i = 0;i < N;i++){ G[i].clear(); } } bool dfs(int u){ for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(!vis[v]){ vis[v] = 1; if(!pre[v] || dfs(pre[v])){ pre[v] = u; return true; } } } return false; } void solve(){ int cnt = 1; for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(s[i][j] == '.') a[i][j] = cnt; else { cnt++; } } cnt++; } cnt = 1; for(int j = 0;j < n;j++){ for(int i = 0;i < n;i++){ if(s[i][j] == '.') b[i][j] = cnt; else { cnt++; } } cnt++; } for(int i = 0;i < n;i++){ for(int j = 0;j < n;j++){ if(s[i][j] == '.'){ G[a[i][j]].push_back(b[i][j]); } } } int ans = 0; for(int i = 1;i < N;i++){ memset(vis,0,sizeof vis); if(dfs(i)) ans++; } printf("%d\n",ans); } int main(){ while(scanf("%d",&n)&&n){ for(int i = 0;i < n;i++){ scanf("%s",s[i]); } init(); solve(); } return 0; }