P2825[HEOI2016/TJOI2016]

发表于 | 分类于 ， ， | 阅读数 次

链接:P2825[HEOI2016/TJOI2016]

Description

  • 在2016年，佳缘姐姐喜欢上了一款游戏，叫做泡泡堂。简单的说，这个游戏就是在一张地图上放上若干个炸弹，看是否能炸到对手，或者
  • 躲开对手的炸弹。在玩游戏的过程中，小H想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个
  • 炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。给定一张
  • nm的网格地图:其中代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。x代表软石头，炸弹的威力可以穿透，不能在此放置
  • 炸弹。#代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。例如：给出14的网格地图xx*，这个地图上最多只能放置一个炸
  • 弹。给出另一个14的网格地图x#，这个地图最多能放置两个炸弹。现在小H任意给出一张nm的网格地图，问你最多能放置多少炸弹。

    Input

  • 第一行输入两个正整数n,m,n表示地图的行数，m表示地图的列数。1≤n,m≤50。接下来输入n行m列个字符，代表网格地图。*的个数不超过
  • n*m个。

    Output

  • 输出一个整数a，表示最多能放置炸弹的个数

    Sample Input

    4 4

    *

    # #
    xxx#

    Sample Output

    5

    题解

  • 提取出每一行和每一列的极长连续不含#的非空字串
  • 显然，炸弹只能放在*上，而放一个就会把它周围清空，这样显然就是二分图最大匹配了
  • 以他们为节点，每一行和每一列连边。跑一个匈牙利就出来了。
  • zz地弄了个骚操作加边，然后WA一万次。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=55;
const int M=3e3;
struct node{
    int v,nxt;
    inline void init(int a,int b){v=a; nxt=b;}
}e[M];
int head[M],cnt,tol,col[N][N],row[N][N],n,m,vis[M],mark[M],ans;
char str[N][N];

inline void add(int a,int b){
    e[++cnt].init(b,head[a]);
    head[a]=cnt;
}

int find(int u){
    for(int i=head[u];i;i=e[i].nxt)if(!vis[e[i].v]){
        vis[e[i].v]=1;
        if(!mark[e[i].v]||find(mark[e[i].v])){
            mark[e[i].v]=u;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n)rep(j,1,m)cin>>str[i][j]; 
    rep(i,1,n)rep(j,1,m)if(str[i][j]!='#'){
        if(j==1||str[i][j-1]=='#')tol++;
        row[i][j]=tol;
    }
    rep(j,1,m)rep(i,1,n)if(str[i][j]!='#'){
        if(i==1||str[i-1][j]=='#')tol++;
        col[i][j]=tol;
    }
    rep(i,1,n)rep(j,1,m)if(str[i][j]=='*')add(row[i][j],col[i][j]);
    rep(i,1,tol){memset(vis,0,sizeof(vis));ans+=find(i);}
    printf("%d\n",ans);
    return 0;
}