HDU - 1045 Fire Net

/****************************************************二分图匹配（匈牙利算法的DFS实现）INIT：g[][]两边定点划分的情况CALL:res=hungary();输出最大匹配数优点：适于稠密图，DFS找增广路快，实现简洁易于理解时间复杂度:O(VE);****************************************************/#include<iostream>using namespace std;#include<cstdio>#include<cstring>const int MAXN=600;int uN,vN; ?//u,v数目int g[MAXN][MAXN];//编号是0~n-1的 int linker[MAXN];bool used[MAXN];bool dfs(int u){ ???int v; ???for(v=0;v<vN;v++) ???????if(g[u][v]&&!used[v]) ???????{ ???????????used[v]=true; ???????????if(linker[v]==-1||dfs(linker[v])) ???????????{ ???????????????linker[v]=u; ???????????????return true; ???????????} ???????????} ?????return false; ?} ???int hungary(){ ???int res=0; ???int u; ???memset(linker,-1,sizeof(linker)); ???for(u=0;u<uN;u++) ???{ ???????memset(used,0,sizeof(used)); ???????if(dfs(u)) ?res++; ???} ????return res; ??}char s[10][10];int mapsa[10][10],mapsb[10][10];int main(){ ???int n; ???while(scanf("%d",&n)!=EOF&&n){ ???????int l,r;int j; ???????int numl=0,numr=0; ???????memset(g,0,sizeof(g)); ???????for (int i=1;i<=n;i++){ ???????????scanf("%s",s[i]+1); ???????} ???????for (int i=1;i<=n;i++){ ???????????for (int j=1;j<=n;j++){ ???????????????mapsa[i][j]=mapsb[i][j]=-1; ???????????} ???????} ???????for (int i=1;i<=n;i++){ ???????????for (j=1;j<=n;j++){ ???????????????if (s[i][j]==‘.‘){ ???????????????????numl++; ???????????????????for (;j<=n&&s[i][j]==‘.‘;j++) mapsa[i][j]=numl; ???????????????} ???????????} ???????} ???????for (int i=1;i<=n;i++){ ???????????for (j=1;j<=n;j++){ ???????????????if (s[j][i]==‘.‘){ ???????????????????numr++; ???????????????????for (;j<=n&&s[j][i]==‘.‘;j++) mapsb[j][i]=numr; ???????????????} ???????????} ???????} ???????for (int i=1;i<=n;i++){ ???????????for (int j=1;j<=n;j++){ ???????????????if (mapsa[i][j]<0||mapsb[i][j]<0) continue; ???????????????g[mapsa[i][j]-1][mapsb[i][j]-1]=1; ???????????} ???????} ???????uN=numl,vN=numr; ???????int ans=hungary(); ???????printf("%d\n",ans); ???} ???return 0;}