当前位置:首页 > 图论 > 二分图 > 正文
BZOJ4554[Tjoi2016&Heoi2016]游戏
1890+

题目大意:炸弹炸的范围同一行和一列,一个n*m的地图,有软石头和硬石头,硬石头可以阻挡炸到穿透,软石头不行,问在空位上至多可以放多少个炸弹?

题目描述

在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

解题思路

如果不考虑列,如果一行有空位,那么至少可以放1个炸弹;如果中间有硬石头阻挡,那么硬石头后面的空位也可以继续放炸弹。现在,把每一行炸弹按行穿透的每一个范围分别看成一个连通块,编号为1到x,那么不考虑列攻击的话,可以放x个炸弹。

考虑列的话,因为连通块可能占不止一列,那么炸弹就有列可以选了,到底选哪一列呢?不管了,选错了可以后悔就行!用二分图匹配每个炸弹选哪一列!由于同一列也可以放多个炸弹,列被选了之后,可能可以再选的,因此不是连通块跟列进行二分图匹配,而是行连通块跟列连通块进行匹配。

同样的,列连通块也编号。如果mp[i][j]是*,那么这里可以放炸弹,会炸弹行连通块x和列连通块y,每个连通块只能被炸一次,最大匹配即是最大可放炸弹数。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,,,

BZOJ4554[Tjoi2016&Heoi2016]游戏:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!