#ABC325C. 传感器

传感器

题目描述

\hspace{15pt}给定一个 n×mn\times m 的网格。字符 \texttt{`#'} 表示传感器,字符 ‘.’\texttt{`.'} 表示空地。

\hspace{15pt}上下左右以及四个斜对角方向相邻的传感器会互相连接,连接关系可以传递。若两个位置为 (x,y)(x,y) 和 (x′,y′)(x',y'),则直接相邻的条件为 max⁡{∣x−x′∣,∣y−y′∣}=1\max\{|x-x'|,|y-y'|\}=1。请统计传感器形成的连通块数量。

输入格式

\hspace{15pt}第一行输入两个整数 n,m(1≦n,m≦103)n,m\left(1\leqq n,m\leqq10^3\right)。

\hspace{15pt}此后 nn 行,每行输入一个长度为 mm、仅含 \texttt{`#'} 和 ‘.’\texttt{`.'} 的字符串,代表一行网格。

输出格式

\hspace{15pt}输出一个整数,代表传感器连通块数量。没有传感器时输出 00。

测试样例

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

样例 1 解释

\hspace{15pt}位置 {(1,2),(1,3),(2,4),(3,5),(3,6)}\{(1,2),(1,3),(2,4),(3,5),(3,6)\} 通过斜对角或边相邻形成一块;(4,1)(4,1) 单独形成一块;(4,3)(4,3) 和 (5,3)(5,3) 形成一块,共 33 块。

3 3
#.#
.#.
#.#
1
4 2
..
..
..
..
0
5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####
7