Lake Counting
Time Limit:1000MS? Memory Limit:65536K
Total Submit:1360 Accepted:629

Description
Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) 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.

Input
* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: M 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.

Output
* Line 1: The number of ponds in Farmer John's field.

Sample Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Sample Output

3

Hint
OUTPUT DETAILS:

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

Source
USACO 2004 November

#include? < iostream >
using ? namespace ?std;

const ? int ?MAX? = ? 102 ;
int ?g[MAX][MAX];

void ?travel( int ?i,? int ?j)
{
???? int ?incr[ 8 ][ 2 ]? = ? { { 0 , - 1 } ,? { 1 , - 1 } ,? { 1 , 0 } ,? { 1 , 1 } ,? { 0 , 1 } ,? { - 1 , 1 } ,? { - 1 , 0 } ,? { - 1 , - 1 } } ;
???? int ?k;
???? int ?tmpI,?tmpJ;
???? for ?(k = 0 ;?k < 8 ;?k ++ )? {
????????tmpI? = ?i? + ?incr[k][ 0 ];
????????tmpJ? = ?j? + ?incr[k][ 1 ];
???????? if ?(g[tmpI][tmpJ]? == ? 1 )? {
????????????g[tmpI][tmpJ]? = ? - 1 ;
????????????travel(tmpI,?tmpJ);
????????}
????}
}

int ?main()
{
???? int ?n,?m;
???? int ?i,?j;
???? int ?ans? = ? 0 ;
???? char ?t;
????cin? >> ?n? >> ?m;
???? for ?(i = 0 ;?i <= m + 1 ;?i ++ )? {
????????g[ 0 ][i]? = ? - 1 ;
????????g[n + 1 ][i]? = ? - 1 ;
????}
???? for ?(i = 0 ;?i <= n + 1 ;?i ++ )? {
????????g[i][ 0 ]? = ? - 1 ;
????????g[i][m + 1 ]? = ? - 1 ;
????}
???? for ?(i = 1 ;?i <= n;?i ++ )? {
???????? for ?(j = 1 ;?j <= m;?j ++ )? {
????????????cin? >> ?t;
???????????? if ?(t? == ? ' W ' )? {
????????????????g[i][j]? = ? 1 ;
????????????} ? else ? {
????????????????g[i][j]? = ? 0 ;
????????????}
????????}
????}
???? for ?(i = 1 ;?i <= n;?i ++ )? {
???????? for ?(j = 1 ;?j <= m;?j ++ )? {
???????????? if ?(g[i][j]? == ? 1 )? {
????????????????ans ++ ;
????????????????g[i][j]? = ? - 1 ;
????????????????travel(i,?j);
????????????}
????????}
????}
????cout? << ?ans? << ?endl;
???? return ? 0 ;
}