P2825 [HEOI2016/TJOI2016]游戏

    • 161通过
    • 421提交
  • 题目提供者 Drench 站长团
  • 评测方式 云端评测
  • 标签 二分图 最大匹配 网络流 连通块 各省省选 2016 河北
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输入输出格式

    输入格式:

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    4 4
    #∗∗∗
    ∗#∗∗
    ∗∗#∗
    xxx#
    输出样例#1: 复制
    5
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。