AT_abc450_c.[ABC450C] Puddles

普及-

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

有一个网格,其中有 HH 行和 WW 列。
如果 Si,jS_{i,j} 是 #,那么位于从上往下 ii 行和从左往右 jj 列的单元格就会被涂成黑色;如果 Si,jS_{i,j} 是 .,那么该单元格就会被涂成白色。

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

下面是更正式的说明。

我们把从上往下第 ii 行,从左往右第 jj 列的单元格称为单元格 (i,j)(i, j)。
当且仅当 ∣i−i′∣+∣j−j′∣=1|i-i'|+|j-j'|=1 时,两个单元格 (i,j)(i, j) 和 (i′,j′)(i', j') 被认为是相邻的。
当且仅当对于白色单元格的连通集合 CC 中的任意两个单元格 cc 和 c′c',cc 可以通过重复移动到 CC 中的相邻单元格到达 c′c' 时,才可以说白色单元格的集合 CC 是连通的。
白色单元格的非空最大连通集合称为白色单元格的连通部分。

求不包含网格最外边(即第 11 行、第 HH 行、第 11 列和第 WW 列)的白色单元格的连通部分的个数。

输入格式

输入内容由标准输入法提供,格式如下

HH WW
S1,1S1,2…S1,WS_{1,1}S_{1,2}\dots S_{1,W}
⋮\vdots
SH,1SH,2…SH,WS_{H,1}S_{H,2}\dots S_{H,W}

输出格式

输出答案。

输入输出样例

  • 输入#1

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

    输出#1

    2
  • 输入#2

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

    输出#2

    4

说明/提示

样例解释 #1

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

限制因素

  • 3≤H,W≤1033 \leq H, W \leq 10^3
  • HH 和 WW 是整数
  • Si,jS_{i,j} 是 # 或 .

输入解题思路,AI测评打分。不知道怎么写?

首页