【NOIP2016模拟7.12】游戏

Description

Input

这个地图

Output

对应的答案

Data Constraint

n,m<=50

Solution

记得之前做过一道题：小行星带
这题也差不多，被#分开行当做不同的行，例如 * #**当做两行。列也同样处理。行和列相交的地方连边，求二分图匹配即可。

Code

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 2610
using namespace std;
int a[60][60];
int n,m,tot=0,ans=0,b[N],last[N*200],next[N*200],to[N*200],st,bz[N];
void putin(int x,int y)
{
next[++tot]=last[x];last[x]=tot;to[tot]=y;
}
int dg(int x)
{
if(bz[x]==st) return 0;bz[x]=st;
for(int i=last[x];i;i=next[i])
    {
int y=to[i];
if(b[y]==0||dg(b[y])){b[y]=x;return 1;}
    }
return 0;
}
int main()
{
    freopen("4612.in","r",stdin);
    scanf("%d%d",&n,&m);
    fo(i,1,n)
    {
        char s[N];
        scanf("%s",s+1);
        fo(j,1,m)
        {
            a[i][j]=s[j];
if(s[j]=='*'){
int x=i-1,y=j-1;
for(;x>0&&a[x][j]!='#';x--);
for(;y>0&&a[i][y]!='#';y--);
                putin((x)*(m+1)+j,(i)*(m+1)+y);
            }
        }
    }
    ans=0;
    fo(i,0,n)
        fo(j,0,m)
if(i==0||j==0||a[i][j]=='#')
        {
            st++;ans+=dg((i)*(m+1)+j);
        }
printf("%d",ans);
}