2084: Alban's search for clean water

文件提交:无需freopen 内存限制:512 MB 时间限制:3.000 S
评测方式:普通裁判 命题人:
提交:1 解决:1

题目描述

On the distant planet of Naboo, Jedi Knight Alban faces a dire challenge. The planet's main oceans have been polluted by Trade Federation chemicals, but legend holds that pure water sources, vital for restoring the planet's ecological balance, still exist in some isolated inland lakes.

Alban has obtained a detailed map of a rectangular region on Naboo. He divides this region into $H$ sections from north to south and $W$ sections from east to west. The section at the northwest corner is (1,1), and the section $i$-th from the north and $j$-th from the east is $(i,j)$. Each section is either land or an area covered by water.

Two water sections are considered connected if they are adjacent in the east-west or north-south direction. If sections can reach each other by passing through a series of connected water sections, they are connected. Water sections located on the outermost border of the region, and any water sections connected to them, are linked to the polluted ocean.

Alban needs to find the pure, unpolluted lakes. He defines: A set of connected water sections is considered a pure lake if it is not connected to the polluted ocean.

Jedi Insight: Only those bodies of water that are completely surrounded by land and isolated from the external polluted ocean can possibly maintain their original pure state.

For example, in the diagram below, # represents a land section, and . represents a water section. The set of shaded sections (2,2), (2,3), (3,2) and the set of sections (3,12), (3,13) each constitute a pure lake. In total, there are 2 pure lakes. Because these lakes are isolated from the polluted ocean, they may hold precious pure water.

输入

$$\begin{aligned} & H \; W \\ & row_1 \\ & row_2 \\ & ... \\ & row_H \end{aligned}$$
  • The first line gives $H$ (number of north-south sections) and $W$ (number of east-west sections), satisfying $1 \leq H, W \leq 200$.

  • The following $H$ lines each contain a string of length $W$, composed of # and ., where # represents land and . represents water.

输出

Output the number of unpolluted lakes.

样例输入

4 14
###...###..##.
#..#..##..####
#.##.##..##..#
###..#########

样例输出

2

提示

来源/分类