题目链接:
zoj 1654
题目大意: 给出NxM的地图,地图上有空地,草地和墙
要在空地上放置机器人,机器人可向上下左右四个方向发射激光
且防止的机器人不会被其他机器人的激光射到,机器人可以穿过草地但不能穿墙
问可以放置机器人的最大数目
解题思路: 先把同一行的空地和草地构成块(中间无墙),若中间有墙则可以构成多个块
再把列按同样的方式分块,行的块作为X集合,列的块作为Y集合
行与列的块有相交的,则是两个集合的连线
因为每个块只能放置一个机器人,选择最优的策略
接下来就是二分匹配的问题,找最大的匹配数
代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 2503
int n,m,k1,k2,edge[MAX][MAX],maph[53][53],mapl[53][53],cx[MAX],cy[MAX],visit[MAX];
char ch[53][53];
int DFS(int u) //匈牙利算法寻找增广轨
{
int i;
for(i=1;i<=k2;i++)
{
if(!visit[i]&&edge[u][i])
{
visit[i]=1;
if(!cy[i]||DFS(cy[i]))
{
cy[i]=u;
cx[u]=i;
return 1;
}
}
}
return 0;
}
int main()
{
int i,i1,j,j1,j2,sum,t;
scanf("%d",&t);
for(i1=1;i1<=t;i1++)
{
sum=0;
memset(cx,0,sizeof(cx));
memset(cy,0,sizeof(cy));
memset(ch,0,sizeof(ch));
memset(edge,0,sizeof(edge));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%s",ch[i]);
}
memset(maph,0,sizeof(maph));
memset(mapl,0,sizeof(mapl));
for(i=0,k1=0;i<n;i++) //行处理
{
for(j=0;j<m;j++)
{
if(ch[i][j]=='o'&&!maph[i][j])
{
k1++;
j1=j2=j;
while(j1>=0&&j1<m)
{
if(ch[i][j1]=='#')
break;
maph[i][j1]=k1;
j1--;
}
while(j2>=0&&j2<m)
{
if(ch[i][j2]=='#')
break;
maph[i][j2]=k1;
j2++;
}
}
}
}
for(i=0,k2=0;i<m;i++) //列处理
{
for(j=0;j<n;j++)
{
if(ch[j][i]=='o'&&!mapl[j][i])
{
k2++;
j1=j2=j;
while(j1>=0&&j1<n)
{
if(ch[j1][i]=='#')
break;
mapl[j1][i]=k2;
j1--;
}
while(j2>=0&&j2<n)
{
if(ch[j2][i]=='#')
break;
mapl[j2][i]=k2;
j2++;
}
}
}
}
for(i=0;i<n;i++) //建立二分图
{
for(j=0;j<m;j++)
{
if(maph[i][j]&&mapl[i][j]&&ch[i][j]=='o') //**空地才能放
edge[maph[i][j]][mapl[i][j]]=1;
}
}
for(i=1;i<=k1;i++)
{
if(!cx[i])
{
memset(visit,0,sizeof(visit));
sum+=DFS(i); //匈牙利增广轨
}
}
printf("Case :%d\n",i1);
printf("%d\n",sum);
}
return 0;
}