#1751. [Usaco2005 qua] Lake Counting

[Usaco2005 qua] Lake Counting

题目描述

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N×MN \times M squares. Each square contains either water (W) or dry land (.).

Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors. Given a diagram of Farmer John's field, determine how many ponds he has.

输入格式

  • Line 11: Two space-separated integers: NN and MM.
  • Lines 2N+12 \sim N + 1: MM characters per line representing one row of Farmer John's field. Each character is either W or .. The characters do not have spaces between them.

输出格式

  • Line 11: The number of ponds in Farmer John's field.
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
3

样例说明

There are three ponds: one in the upper left, one in the lower left, and one along the right side.

数据规模与约定

对于 100%100\% 的数据:1N1001 \leq N \leq 1001M1001 \leq M \leq 100

题目来源

Usaco2005 qua