POJ-2386-Lake Counting-DFS-easy.txt

/**
 *POj-2386-Lake Counting
 *xuchen
 *2015-11-02 20:47:09
**/
/**
**/
#include "stdio.h"
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const int N = 105;
struct point{
	int x, y;
};

int map[N][N];
bool vis[N][N];
int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {1, -1}, {0, -1}, {0, 1}, {1, 0}, {1, 1}};
int m, n;
char s[N];
int ans;

void dfs(int i, int j)
{
	int mi, mj;
	vis[i][j] = true;
	for(int k=0; k<8; k++)
	{
		mi = i+dir[k][0];
		mj = j+dir[k][1];
		if(map[mi][mj]==1 && !vis[mi][mj])
		{
			dfs(mi, mj);
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	
	for(int i=1; i<=n; i++)
	{
		scanf("%s", s);
		for(int j=0; j<m; j++)
		{
			if(s[j]=='W')
				map[i][j+1] = 1;
		}
	}
	
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
		{
			if(map[i][j]==1 && !vis[i][j])
			{
				ans++;
				dfs(i, j);
			}
		}
	printf("%d\n", ans);
	return 0;
}