You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

执信楼前的草坪被改造成了一个 $H$ 行 $W$ 列的由若干无线传感器 # 和空地 . 组成的网格。一个无线传感器会与其水平、垂直、对角线相邻（八联通）的传感器协同工作，组成一个更大的传感器网络。

把上面的描述形式化：设 $A$ 传感器的位置为 $(x_a,y_a)$，$B$ 传感器的位置为 $(x_b,y_b)$，$A$ 和 $B$ 八联通 $\iff$ $max(|x_a-x_b|,|y_a-y_b|) = 1$。此时 $A$ 和 $B$ 属于同一个传感器网络。

网格的情况由 $H$ 个长度均为 $W$ 的字符串$S_1, S_2, \dots, S_H$ 给出，求该网格中的传感器网络的数量。注意：

• 一个不与其他传感器八联通的孤立的传感器，自己组成一个网络。
• 若 $A$ 和 $B$ 属于同一个网络，$B$ 和 $C$ 属于同一个网络，那么 $A$ 和 $C$ 也属于同一个网络。

输入格式

第一行为两个整数；后面 $H$ 行，每行一个长度为 $W$ 的字符串：

$H$ $W$

$S_1$

$S_2$

$\vdots$

$S_H$

输出格式

传感器网络的数量。

样例 #1

样例输入 #1

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

样例输出 #1

3

样例 #2

样例输入 #2

3 3
#.#
.#.
#.#

样例输出 #2

1

样例 #3

样例输入 #3

4 2
..
..
..
..

样例输出 #3

0

样例 #4

样例输入 #4

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

样例输出 #4

7

提示

数据范围

• $1\ \leq\ H,\ W\ \leq\ 1000$
• $H,\ W$ 是整数
• $S_i$ 长度为 $W$，只包含 # 或 .