[文章目录]
Description
在2016年，佳缘姐姐喜欢上了一款游戏，叫做泡泡堂。简单的说，这个游戏就是在一张地图上放上若干个炸弹，看是否能炸到对手，或者躲开对手的炸弹。在玩游戏的过程中，小H想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。给定一张n*m的网格地图:其中*代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。x代表软石头，炸弹的威力可以穿透，不能在此放置炸弹。#代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。例如：给出1*4的网格地图 *xx* ，这个地图上最多只能放置一个炸弹。给出另一个1*4的网格地图*x#*，这个地图最多能放置两个炸弹。现在小H任意给出一张n*m的网格地图，问你最多能放置多少炸弹.n,m<=50
对于一个炸弹的放置相当于废了一个行和一个列，对于硬石头分开的行和列看做两部分，拆开后，问题就等价于求行和列的最大匹配了。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,s,t,ans;
char mp[70][70];
int dx[70][70],dy[70][70],tot;
int head[10000],to[20000],nxt[20000],f[20000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[10000];
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof dis);
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
int main()
{
scanf("%d%d",&n,&m); s=1; t=2; tot=2;
for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);
int fl=0;
for(int i=1;i<=n;++i)
{
fl=1;
for(int j=1;j<=m;++j)
{
if(mp[i][j]=='*')
{
if(fl) dy[i][j]=++tot,add(tot,t,1),fl=0;
else dy[i][j]=tot;
}
else if(mp[i][j]=='#') fl=1;
}
}
for(int j=1;j<=m;++j)
{
fl=1;
for(int i=1;i<=n;++i)
{
if(mp[i][j]=='*')
{
if(fl) dx[i][j]=++tot,add(s,tot,1),fl=0;
else dx[i][j]=tot;
}
else if(mp[i][j]=='#') fl=1;
}
}
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
if(dx[i][j]&&dy[i][j])
add(dx[i][j],dy[i][j],1);
while(bfs()) ans+=dinic(s,1<<30);
printf("%d",ans);
return 0;
}