题意:一个阵地可以向四周扫射,求出来最多能修多少个阵地,墙不可以被扫射透,阵地不能同行或者或者列(有墙隔着例外)
分析:很久以前就做过这道题。。当时是练习深搜来着,不过时间复杂度比较高,现在再看突然发现原来可以用二分图匹配来做,时间soso的
******************************************************************
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; const int MAXN = ;
const int oo = 1e9; bool G[MAXN][MAXN], used[MAXN];
int p[MAXN], x, y;
struct node{int x, y;}a[MAXN][MAXN]; bool Find(int u)
{///匈牙利算法匹配
for(int i=; i<=y; i++)
{
if(G[u][i] && used[i] == false)
{
used[i] = true;
if(!p[i] || Find(p[i]))
{
p[i] = u;
return true;
}
}
} return false;
} int main()
{
int N; while(scanf("%d", &N), N)
{
int i, j;
char s[MAXN][MAXN]; for(i=; i<N; i++)
scanf("%s", s[i]); x = y = ; for(i=; i<N; i++)
for(j=; j<N; j++)
{///把图分割,以相连的‘.’为行和列重新分配编号
if(s[i][j] == '.')
{
if(j == || s[i][j-] == 'X')
x++;
a[i][j].x = x;
}
if(s[j][i] == '.')
{
if(j == || s[j-][i] == 'X')
y++;
a[j][i].y = y;
}
} memset(G, , sizeof(G)); for(i=; i<N; i++)
for(j=; j<N; j++)
{
if(s[i][j] == '.')
{
int u = a[i][j].x;
int v = a[i][j].y;
G[u][v] = true;///用行匹配列
}
} int ans = ;
memset(p, , sizeof(p));
for(i=; i<=x; i++)
{
memset(used, false, sizeof(used));
if( Find(i) == true )
ans++;
} printf("%d\n", ans);
} return ;
}