← 返回题目列表

AtCoder · abc325_c

E. 传感器

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

网格上放置了零个或多个传感器 H 行和 W 列。让 (i, j) 表示中的方块 i从顶部开始的第行和 j左起第 列。
每个方格是否包含传感器由字符串给出 S_1, S_2, \ldots, S_H,每个长度 W. (i, j) 包含传感器当且仅当 j- 第一个字符 S_i is #.
这些传感器与水平、垂直或对角相邻的方块中的其他传感器交互,并作为一个传感器运行。 这里,一个细胞 (x, y) 和一个单元格 (x', y') 被称为水平、垂直或对角相邻当且仅当 \max(|x-x'|,|y-y'|) = 1.
请注意,如果传感器 A 与传感器交互 B 和传感器 A 与传感器交互 C,然后是传感器 B 和传感器 C 也互动。

将相互作用的传感器视为一个传感器,找出该网格上的传感器数量。

约束

  • 1 \leq H, W \leq 1000
  • H 和 W 是整数。
  • S_i 是一个长度为 W 其中每个字符是 # or ..

输入

输入由标准输入按以下格式给出:

H W
S_1
S_2
\vdots
S_H

输出

打印答案。


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