Sensors

题目描述

在一个有 $H$ 行 $W$ 列的网格上放置了零个或多个传感器。令 $(i, j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的方格。
每个方格是否包含传感器由长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 给出。当且仅当 $S_i$ 的第 $j$ 个字符为 # 时，方格 $(i, j)$ 包含传感器。
这些传感器会与水平方向、垂直方向或对角线方向相邻的方格中的传感器相互作用，并作为一个传感器一起工作。 这里，当且仅当 $\max(|x-x'|,|y-y'|) = 1$ 时，方格 $(x, y)$ 与方格 $(x', y')$ 被称为在水平方向、垂直方向或对角线方向上相邻。
注意，如果传感器 $A$ 与传感器 $B$ 相互作用且传感器 $A$ 与传感器 $C$ 相互作用，那么传感器 $B$ 与传感器 $C$ 也相互作用。 将相互作用的传感器视为一个传感器，求该网格上传感器的数量。

输入格式

输入由标准输入按如下格式提供： $H$ $W$ $S_1$ $S_2$ $\vdots$ $S_H$

输出格式

输出答案。

5 6
.##...
...#..
....##
#.#...
..#...

3

3 3
#.#
.#.
#.#

1

4 2
..
..
..
..

0

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

7

提示

$1 \leq H, W \leq 1000$ $H$ 和 $W$ 是整数。 $S_i$ 是长度为 $W$ 的字符串，其中每个字符为 # 或 $.$。在将相互作用的传感器视为一个传感器时，存在如下三个传感器：

位于 $(1,2),(1,3),(2,4),(3,5),(3,6)$ 的相互作用的传感器 位于 $(4,1)$ 的传感器 位于 $(4,3),(5,3)$ 的相互作用的传感器

标签: AtCoder|abc325C

来源

AtCoder|abc325C