Lake Counting

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

解题思路

1.深搜或者广搜
2.并查集

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
char arr[105][105];
int x,y;

void dfs(int u,int v){
	if(u<0||u>=x||v<0||v>=y||arr[u][v]=='.') return; //这里要先判断越界与否再判断是否为0
	arr[u][v]='.';
	for(int i=-1;i<2;i++){
		for(int j=-1;j<2;j++){
			if(i==0&&j==0) continue; 
			else dfs(u+i,v+j);
		}
	}
}
int main(){
	
	cin>>x>>y;
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			cin>>arr[i][j];
		}
	}
	int count=0;
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			if(arr[i][j]=='W'){
				count++;
				dfs(i,j);
			}
		}
	}
	cout<<count<<endl;
	return 0;
}