AT_abc450_c.[ABC450C] Puddles
普及-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有一个网格,其中有 H 行和 W 列。
如果 Si,j 是 #,那么位于从上往下 i 行和从左往右 j 列的单元格就会被涂成黑色;如果 Si,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
S1,1S1,2…S1,W
⋮
SH,1SH,2…SH,W
输出格式
输出答案。
输入输出样例
输入#1
5 15 ##########..### #...#######.### ####....###..## ######.######## ########....###
输出#1
2
输入#2
10 22 ###################### ####.################# ###...################ ##.###.##.....######## ##.....##.####.####### .######.#......#.....# .######.#.####.#.##### #########.....##.##### ################.##### ################.....#
输出#2
4
说明/提示
样例解释 #1
有两个这样的区域:由从上至下的第 2 行中的从左至右的第 2,3,4 列的三个单元格组成的区域,以及由从上至下的第 3 行中的从左至右的第 5,6,7,8 列和从上至下的第 4 行中的从左至右的第 7 列共五个单元格组成的区域。
限制因素
- 3≤H,W≤103
- H 和 W 是整数
- Si,j 是
#或.
输入解题思路,AI测评打分。不知道怎么写?