传感器

题目描述

在一个 $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

将相互感应的传感器视为一个传感器时,存在以下三个传感器:

• $(1,2),(1,3),(2,4),(3,5),(3,6)$ 处相互感应的传感器
• $(4,1)$ 处的传感器
• $(4,3),(5,3)$ 处相互感应的传感器

3 3
#.#
.#.
#.#

1

4 2
..
..
..
..

0

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

7

数据范围

• $1 \le H, W \le 1000$
• $H, W$ 为整数
• $S_i$ 是长度为 $W$ 的字符串,每个字符为 # 或 .