分数: 300 点
问题陈述
网格上放置了零个或多个传感器 H 行和 W 列。让 (i, j) 表示中的方块 i从顶部开始的第行和 j左起第 列。
每个方格是否包含传感器由字符串给出 S_1, S_2, \ldots, S_H,每个长度 W. (i, j) 包含传感器当且仅当 j- 第一个字符 S_i is #.
这些传感器与水平、垂直或对角相邻的方块中的其他传感器交互,并作为一个传感器运行。
这里,一个细胞 (x, y) 和一个单元格 (x', y') 被称为水平、垂直或对角相邻当且仅当 \max(|x-x'|,|y-y'|) = 1.
请注意,如果传感器 A 与传感器交互 B 和传感器 A 与传感器交互 C,然后是传感器 B 和传感器 C 也互动。
将相互作用的传感器视为一个传感器,找出该网格上的传感器数量。
约束
- 1 \leq H, W \leq 1000
- H 和 W 是整数。
- S_i 是一个长度为 W 其中每个字符是
#or..
输入
输入由标准输入按以下格式给出:
H W S_1 S_2 \vdots S_H
输出
打印答案。
示例输入 1
5 6 .##... ...#.. ....## #.#... ..#...
示例输出 1
3
当将相互作用的传感器视为一个传感器时,存在以下三个传感器:
- 交互传感器 (1,2),(1,3),(2,4),(3,5),(3,6)
- 传感器位于 (4,1)
- 交互传感器 (4,3),(5,3)
示例输入 2
3 3 #.# .#. #.#
示例输出 2
1
示例输入 3
4 2 .. .. .. ..
示例输出 3
0
示例输入 4
5 47 .#..#..#####..#...#..#####..#...#...###...##### .#.#...#.......#.#...#......##..#..#...#..#.... .##....#####....#....#####..#.#.#..#......##### .#.#...#........#....#......#..##..#...#..#.... .#..#..#####....#....#####..#...#...###...#####
示例输出 4
7