- 科技
- Fire Net HDU - 1045 二分图
连续的一行给一个编号，连续的一列给一个编号，建图。
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<ctime>
#include<algorithm>
#define eps 1e-14
#define pi acos(-1)
#define ll long long
#define RD T*(rand()*2-RAND_MAX)
#define Drand (long double)rand()/RAND_MAX
#define INF 0x3f3f3f3f
using namespace std
;
const int maxn
=5e5+1000;
const int mod
=1e4+7;
int mapr
[5][5],mapc
[5][5];
int g
[20][20];
char Map
[5][5];
int n
,nr
,nc
;
int used
[30],col
[30];
void init()
{
memset(col
,0,sizeof col
);
memset(g
,0,sizeof g
);
memset(mapr
,0,sizeof mapr
);
memset(mapc
,0,sizeof mapc
);
nr
=nc
=0;
}
int dfs(int x
)
{
for(int i
=1;i
<=nc
;i
++){
if(used
[i
]==0 && g
[x
][i
]==1){
used
[i
]=1;
if(col
[i
]==0 || dfs(col
[i
])==1){
col
[i
]=x
;
return 1;
}
}
}
return 0;
}
int Maxmatch()
{
int ans
=0;
for(int i
=1;i
<=nr
;i
++){
memset(used
,0,sizeof used
);
if(dfs(i
))ans
++;
}
return ans
;
}
int main()
{
while(~scanf("%d",&n
)&&n
){
init();
getchar();
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++)
scanf("%c",&Map
[i
][j
]);
getchar();
}
int cnt
=1;
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++){
while(Map
[i
][j
]=='X' && j
<=n
)j
++;
while(Map
[i
][j
]!='X' && j
<=n
){
mapr
[i
][j
]=cnt
;
j
++;
}
cnt
++;
}
}
nr
=cnt
-1;
cnt
=1;
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++){
while(Map
[j
][i
]=='X' && j
<=n
)j
++;
while(Map
[j
][i
]!='X' && j
<=n
){
mapc
[j
][i
]=cnt
;
j
++;
}
cnt
++;
}
}
nc
=cnt
-1;
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++){
if(Map
[i
][j
]!='X')
g
[ mapr
[i
][j
] ][ mapc
[i
][j
] ]=1;
}
}
cout
<<Maxmatch()<<endl
;
}
return 0;
}
