QOJ.ac

QOJ

実行時間制限: 1 s メモリ制限: 2048 MB 満点: 100

#8659. 希巴的变形虫

統計

在一次成功的 Kickstarter 众筹活动后,Sheba Arriba 为她的邮购生物用品公司筹集了足够的资金。“Sheba’s Amoebas” 可以运送已经培育好单细胞生物菌落的培养皿。然而,Sheba 需要能够核实她公司发出的变形虫数量。对于每个培养皿,她都有一张经过预处理的黑白图像,图像中每个变形虫都显示为一个简单的黑色像素闭合环。(环是指一组最小的黑色像素集合,其中每个像素与集合中的恰好另外两个像素相邻;相邻意味着共享像素的边或角。)图像中的所有黑色像素都属于某个环。

Sheba 希望你编写一个程序,计算黑色和白色像素组成的矩形阵列中的闭合环数量。图像中没有两个闭合环接触或重叠。已知有一种特别讨厌的食人变形虫会包围并吞噬其邻居;因此,可能会出现变形虫内部还有变形虫的情况。例如,图 H.1 中的每张图像都包含四个变形虫。

图 H.1:两个培养皿,每个包含四个变形虫。

输入格式

输入的第一行包含两个整数 $m$ 和 $n$ ($1 \le m, n \le 100$)。接下来是 $m$ 行,每行包含 $n$ 个字符。‘#’ 表示黑色像素,‘.’ 表示白色像素。对于每个黑色像素,其八个邻居中恰好有两个也是黑色像素。

输出格式

输出一个整数,表示输入中的环数。

样例

样例输入 1

12 12
.##########.
#..........#
#..#...##..#
#.##..#..#.#
#......#.#.#
#....#..#..#
#...#.#....#
#..#...#...#
.#..#.#....#
#....#.....#
#.........#.
.#########..

样例输出 1

4

样例输入 2

12 10
.#####....
#.....#...
#..#..#...
#.#.#.#...
#..#..#...
.#...#....
..###.....
......#...
.##..#.#..
#..#..#...
.##.......
..........

样例输出 2

4

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.