A7703 | [ABC450C] Puddles
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
有一个网格,其中有 $H$ 行和 $W$ 列。
如果 $S_{i,j}$ 是
在由白色单元格组成的四个方向相连的区域中,找出被黑色单元格**包围**的区域的数量。
下面是更正式的说明。
我们把从上往下第 $i$ 行,从左往右第 $j$ 列的单元格称为单元格 $(i, j)$。
当且仅当 $|i-i'|+|j-j'|=1$ 时,两个单元格 $(i, j)$ 和 $(i', j')$ 被认为是相邻的。
当且仅当对于白色单元格的连通集合 $C$ 中的任意两个单元格 $c$ 和 $c'$,$c$ 可以通过重复移动到 $C$ 中的相邻单元格到达 $c'$ 时,才可以说白色单元格的集合 $C$ 是连通的。
白色单元格的非空最大连通集合称为**白色单元格的连通部分**。
求**不包含**网格最外边(即第 $1$ 行、第 $H$ 行、第 $1$ 列和第 $W$ 列)的**白色单元格的连通部分**的个数。
如果 $S_{i,j}$ 是
#,那么位于从上往下 $i$ 行和从左往右 $j$ 列的单元格就会被涂成黑色;如果 $S_{i,j}$ 是 .,那么该单元格就会被涂成白色。在由白色单元格组成的四个方向相连的区域中,找出被黑色单元格**包围**的区域的数量。
下面是更正式的说明。
我们把从上往下第 $i$ 行,从左往右第 $j$ 列的单元格称为单元格 $(i, j)$。
当且仅当 $|i-i'|+|j-j'|=1$ 时,两个单元格 $(i, j)$ 和 $(i', j')$ 被认为是相邻的。
当且仅当对于白色单元格的连通集合 $C$ 中的任意两个单元格 $c$ 和 $c'$,$c$ 可以通过重复移动到 $C$ 中的相邻单元格到达 $c'$ 时,才可以说白色单元格的集合 $C$ 是连通的。
白色单元格的非空最大连通集合称为**白色单元格的连通部分**。
求**不包含**网格最外边(即第 $1$ 行、第 $H$ 行、第 $1$ 列和第 $W$ 列)的**白色单元格的连通部分**的个数。
输入格式
输入内容由标准输入法提供,格式如下
>$H$ $W$
$S_{1,1}S_{1,2}\dots S_{1,W}$
$\vdots$
$S_{H,1}S_{H,2}\dots S_{H,W}$
>$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
10 22 ###################### ####.################# ###...################ ##.###.##.....######## ##.....##.####.####### .######.#......#.....# .######.#.####.#.##### #########.....##.##### ################.##### ################.....#
输出 #2
4
#### 样例解释 #1
有两个这样的区域:由从上至下的第 $2$ 行中的从左至右的第 $2, 3, 4$ 列的三个单元格组成的区域,以及由从上至下的第 $3$ 行中的从左至右的第 $5, 6, 7, 8$ 列和从上至下的第 $4$ 行中的从左至右的第 $7$ 列共五个单元格组成的区域。
#### 限制因素
- $3 \leq H, W \leq 10^3$
- $H$ 和 $W$ 是整数
- $S_{i,j}$ 是
有两个这样的区域:由从上至下的第 $2$ 行中的从左至右的第 $2, 3, 4$ 列的三个单元格组成的区域,以及由从上至下的第 $3$ 行中的从左至右的第 $5, 6, 7, 8$ 列和从上至下的第 $4$ 行中的从左至右的第 $7$ 列共五个单元格组成的区域。
#### 限制因素
- $3 \leq H, W \leq 10^3$
- $H$ 和 $W$ 是整数
- $S_{i,j}$ 是
# 或 .
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?