#abc450c. Puddles

Puddles

【题目描述】

有一个 HHWW 列的网格。
从上往下第 ii 行、从左往右第 jj 列的格子记为 (i,j)(i, j)
Si,jS_{i,j}#,则该格子被涂成黑色;若为 .,则被涂成白色。

我们考虑由白色格子组成的四连通区域(上下左右相邻)。
请找出被黑色格子完全包围的白色连通区域的个数。

更精确地说:

  • 两个格子 (i,j)(i, j)(i,j)(i', j') 被称为相邻,当且仅当 ii+jj=1|i - i'| + |j - j'| = 1
  • 一个白色格子集合 CC 被称为连通,当且仅当对任意两个格子 c,cCc, c' \in C,都可以通过 CC 中相邻格子的移动从 cc 到达 cc'
  • 一个非空的连通白色格子集合,如果不能再加入任何其他白色格子而保持连通性,则称为一个白色连通分量
  • 请你求出那些不包含网格最外圈任何格子的白色连通分量的个数。
    (最外圈指:第 11 行、第 HH 行、第 11 列 或 第 WW 列)

【输入格式】

输入从标准输入按以下格式给出:

H W
S_{1,1}S_{1,2}…S_{1,W}
S_{2,1}S_{2,2}…S_{2,W}
⋮
S_{H,1}S_{H,2}…S_{H,W}

【输出格式】

输出满足条件的白色连通分量的个数。

【约束条件】

  • 3H,W1033 \le H, W \le 10^3
  • HHWW 是整数
  • 每个 Si,jS_{i,j}#.

【样例输入 1】

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

【样例输出 1】

2

【样例 1 解释】

有两个被黑色包围的白色区域:

  • 一个由第 2 行第 2–4 列的 3 个格子组成;
  • 另一个由第 3 行第 5–8 列和第 4 行第 7 列共 5 个格子组成。

【样例输入 2】

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

【样例输出 2】

4