开始: 2026-06-19 17:50:00

26.6春季提高班期末测试

结束: 2026-06-19 20:20:00
当前  2026-06-21 06:03:38  类型: IOI  状态: 已经结束 

P1. 网格图
描述

有一个网格,其中有 H 行和 W 列。  

如果 S_{i,j} 是 `#`,那么位于从上往下 i 行和从左往右 j 列的单元格就会被涂成黑色;如果 S_{i,j} 是 `.`,那么该单元格就会被涂成白色。

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


下面是更正式的说明。

我们把从上往下第 i 行,从左往右第 j 列的单元格称为单元格 (i, j)。  

当且仅当 |i-i'|+|j-j'|=1 时,两个单元格 (i, j)(i', j') 被认为是相邻的。  

当且仅当对于白色单元格的连通集合 C 中的任意两个单元格 cc'c 可以通过重复移动到 C 中的相邻单元格到达 c' 时,才可以说白色单元格的集合 C 是连通的。  

白色单元格的非空最大连通集合称为**白色单元格的连通部分**。

**不包含**网格最外边(即第 1 行、第 H 行、第 1 列和第 W 列)的**白色单元格的连通部分**的个数(就是如果扩出去白色区域不能算)。


输入

第一行两个数字n,m,表示行和列;

接下来是一个n,m的一个网格图;

输出

一个数字表示白色连通块(被黑色包围的)的数量

样例

输入

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

输出

2

输入

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

输出

4
提示

样例解释 #1

有两个这样的区域:由从上至下的第 2 行中的从左至右的第 2, 3, 4 列的三个单元格组成的区域,以及由从上至下的第 3 行中的从左至右的第 5, 6, 7, 8 列和从上至下的第 4 行中的从左至右的第 7 列共五个单元格组成的区域。

#### 限制因素

- 3 \leq H, W \leq 10^3

- HW 是整数

- S_{i,j} 是 `#` 或 `.`


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交