#abc450c. Puddles
Puddles
【题目描述】
有一个 行 列的网格。
从上往下第 行、从左往右第 列的格子记为 。
若 为 #,则该格子被涂成黑色;若为 .,则被涂成白色。
我们考虑由白色格子组成的四连通区域(上下左右相邻)。
请找出被黑色格子完全包围的白色连通区域的个数。
更精确地说:
- 两个格子 和 被称为相邻,当且仅当 。
- 一个白色格子集合 被称为连通,当且仅当对任意两个格子 ,都可以通过 中相邻格子的移动从 到达 。
- 一个非空的连通白色格子集合,如果不能再加入任何其他白色格子而保持连通性,则称为一个白色连通分量。
- 请你求出那些不包含网格最外圈任何格子的白色连通分量的个数。
(最外圈指:第 行、第 行、第 列 或 第 列)
【输入格式】
输入从标准输入按以下格式给出:
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}
【输出格式】
输出满足条件的白色连通分量的个数。
【约束条件】
- 和 是整数
- 每个 是
#或.
【样例输入 1】
5 15
###############
#..###...#####
#...#####....#
##.#########.#
###############
【样例输出 1】
2
【样例 1 解释】
有两个被黑色包围的白色区域:
- 一个由第 2 行第 2–4 列的 3 个格子组成;
- 另一个由第 3 行第 5–8 列和第 4 行第 7 列共 5 个格子组成。
【样例输入 2】
10 22
######################
##.##################
##...################
##.###.##.....#######
##.....##.####.######
##.#......#.....#.###
##.######.#.####.#.##
##.##############...
#####################
#####################
【样例输出 2】
4