​时间限制​: 2秒 / ​内存限制​: 1024MB

​分数​: 300分

问题描述

在一个由 H 行和 W 列组成的网格中，存在零个或多个传感器。假设 (i,j) 表示网格中第 i 行、第 j 列的格子。

每个格子是否包含传感器由以下的字符串给出：

• ​S₁, S₂, ..., Sₖ​，每个字符串的长度为 ​W​。
• 如果第 i 行、第 j 列的格子中包含传感器，那么 Sᵢ[j] 为 ​**#​，否则为 ​.**​。

这些传感器与相邻的传感器（包括水平、垂直或对角线方向）进行交互，并作为一个传感器工作。也就是说，两个格子 (x, y) 和 (x', y') 如果在水平方向、垂直方向或者对角线方向上相邻（即：max(|x - x'|, |y - y'|) = 1），则它们互相交互。

需要注意的是，如果传感器 A 与传感器 B 交互，且传感器 A 与传感器 C 交互，那么传感器 B 和传感器 C 也会交互。

将这些交互的传感器视为一个传感器，要求计算网格中一共有多少个独立的传感器。

输入格式

输入的格式如下：

H W
S₁
S₂
...
Sᵀ

• H 和 W 为网格的行数和列数，满足 ​1 ≤ H, W ≤ 1000​。
• 接下来的 H 行每行包含一个长度为 W 的字符串 ​Sᵢ​，每个字符为 # 或 ​**.**​。

输出格式

输出一个整数，表示网格中传感器的个数。

示例输入 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