← 返回题目列表

AtCoder · abc450_c

E. 水坑

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

分数: 300 点

问题陈述

有一个网格 H 行和 W 列。
的单元格 i从顶部开始的第行和 j左起第 列被涂成黑色,如果 S_{i,j} is #,如果 S_{i,j} is ..

在由白色单元组成的四个方向连接的区域中,找到被黑色单元包围的区域的数量。

以下是更正式的声明。

我们表示位于 i从顶部开始的第行和 j从左侧算起的第 列作为单元格 (i, j).
两个细胞 (i, j) 和 (i', j') 被称为相邻当且仅当 |i-i'|+|j-j'|=1.
一套 C 的白细胞被认为是连接的当且仅当对于任何两个细胞 c 和 c' in C,可以从 c to c' 通过重复移动到相邻单元格 C.
最大的非空连通白细胞集称为白细胞连通分量。
求网格最外边界(即行中)不包含任何单元格的白色单元格的连通分量数 1,行 H,列 1或列 W).

约束

  • 3 \leq H, W \leq 10^3
  • H 和 W 是整数。
  • S_{i,j} is # or ..

输入

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

H W
S_{1,1}S_{1,2}\dots S_{1,W}
\vdots
S_{H,1}S_{H,2}\dots S_{H,W}

输出

输出答案。


示例输入 1

5 15
##########..###
#...#######.###
####....###..##
######.########
########....###

示例输出 1

2

有两个这样的区域:由行中的三个单元格组成的区域 2 从顶部和列 2, 3, 4 从左起,总共由五个单元格组成的区域:列 5, 6, 7, 8 从行左侧开始 3 从顶部和列 7 从行左侧开始 4 从顶部。


示例输入 2

10 22
######################
####.#################
###...################
##.###.##.....########
##.....##.####.#######
.######.#......#.....#
.######.#.####.#.#####
#########.....##.#####
################.#####
################.....#

示例输出 2

4