Lake Counting(POJ 2386)

原题目如下：

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

解题思路：

这道题是一道非常经典的深度优先算法题目，具体思路为：我们先任意找到一个W，从那个W开始进行遍历，在遍历时寻找下一个W，直到没有W为止，算作一个水坑。并且，当我们遍历到W时，我们需要将这个W改为. 目的是为了不重复进行遍历。注意，在每一次示例之后，都要清一次count。不然的话上一个示例的水坑数将导致这一次的水坑数不正确。（其实，这道题的基本思想就是图的遍历)(实在不懂的话，阅读一下代码再结合实例就会明白)

代码如下：

#include <iostream>
#include <cstdio>
using namespace std;
char graph[100][100];   
int n,m;
pair<int, int> Move[3][3];   //定义一个pair类型的数组，代表能移动的方向（需要用field数组构造)(分别对应着九个移动的方向)
int field[3] = { -1,0,1 };   
void dfs(int x, int y);    //代表进行深度优先搜索的函数

void dfs(int x, int y)
{
	int movex, movey;          //定义移动后的x，y坐标
	int k, l;
	graph[x][y] = '.';   //将当前所在的位置设置为没有积水
	for (k = 0; k < 3; k++)
	{
		for (l = 0; l < 3; l++)
		{
			movex = x + Move[k][l].first;
			movey = y + Move[k][l].second;
			if (movex >= 0 &&  movex < n && movey >= 0 && movey < m && graph[movex][movey] == 'W')    //当在图中移动时，x的移动，代表了坐标向上或下移动了多少。y的移动，代表了坐标向左或向右移动了多少
			{
				dfs(movex, movey);
			}
		}
	}
	
}
int main()
{
	int i, j;
	int count=0;
	while (scanf("%d %d",&n,&m)!=EOF)
	{
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				cin >> graph[i][j];
			}
		}
		for (i = 0; i < 3; i++)
		{
			for (j = 0; j < 3; j++)
			{
				Move[i][j] = make_pair(field[i], field[j]);
			}
		}
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
			{
				if (graph[i][j] == 'W')   //再图中进行搜索，看有没有值为W的节点，如果有，从这个节点开始遍历
				{
					dfs(i, j);     //对这个节点以及跟这个节点的所有联通节点，进行深度优先搜索
					count++;       //一次深度优先搜索之后，水坑数就+1（这个地方不懂的话，就参考上面的输入实例自己思考一下把)
				}
			}
		}
		printf("%d\n", count);
		count = 0;
	}
}