← 返回题目

题库练习游戏

← 上一题下一题 →

A2169 | $游戏$

来源省选 / 2016

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

小 H 想到了这样一个问题：当给定一张地图，在这张地图上最多能放上多少个炸弹能使得任意两个炸弹之间不会互相炸到。炸弹能炸到的范围是该炸弹所在的一行和一列，炸弹的威力可以穿透软石头，但是不能穿透硬石头。 给定一张n*m 的网格地图:其中 ` * 代表空地，炸弹的威力可以穿透，可以在空地上放置一枚炸弹。 x 代表软石头，炸弹的威力可以穿透，不能在此放置炸弹。 # 代表硬石头，炸弹的威力是不能穿透的，不能在此放置炸弹。例如：给出 1 * 4 的网格地图 *xx* ，这个地图上最多只能放置一个炸弹。给出另一个1 * 4 的网格地图 *x#* `，这个地图最多能放置两个炸弹。 现在小 H 任意给出一张 n * m 的网格地图，问你最多能放置多少炸弹。

输入格式

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

输出格式

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

输入输出样例

输入 #1

4 4
#***
*#**
**#*
xxx#

输出 #1

C++ 编辑器

输入

输出