分数: 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