挑战程序设计竞赛 2.1章习题 POJ 2386 Lake Counting

https://vjudge.net/problem/POJ-2386

由于最近的降雨，水在农夫约翰的田地上聚集，在这片田地中，每个方块都被表示为一个 N x M（1 ≤ N ≤ 100；1 ≤ M ≤ 100）的矩形。
每个方块可以是水（'W'）或干地（'.'）。农夫约翰想弄清楚他的田地上形成了多少个池塘。
池塘是由含有水的相连方块组成的集合，其中一个方块被认为与其八个邻居方块相邻。

给定农夫约翰田地的图表，请确定他有多少个池塘。
输入：

第1行：两个由空格分隔的整数：N 和 M
第2至第 N+1 行：每行 M 个字符，表示农夫约翰田地的一行。每个字符可以是 'W' 或 '.'，字符之间没有空格。 输出：
第1行：农夫约翰田地中池塘的数量。

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

数据比较小 可以锻炼下BFS 和DFS

const int N = 150;
char gra[N][N];
int n, m;
int ans;

int addx[] = { 1,-1,0,0,1,-1,1,-1 };
int addy[] = { 0,0,1,-1,1,-1,-1,1 };


void dfs(int x, int y) {
	if (gra[x][y] == 'W')gra[x][y] = '.';

	for (int i = 0; i < 8; i++) {
		int newx = x + addx[i]; int newy = y + addy[i];
		if (newx >= 0 && newx < n && newy >= 0 && newy < m && gra[newx][newy] == 'W') {
			dfs(newx, newy);
		}
	}
}

void solve() {
	ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (gra[i][j] == 'W') {
				dfs(i, j);
				ans++;
			}
		}
	}
	cout << ans << endl;
}

void bfs(int x,int y) {
	queue<vector<int> > q;
	vector<int> t; t.push_back(x); t.push_back(y);
	q.push(t);

	while (!q.empty()) {
		int currx = q.front()[0];
		int curry = q.front()[1];
		q.pop();

		if (gra[currx][curry] == 'W')gra[currx][curry] = '.';
		else { continue; }

		for (int i = 0; i < 8; i++) {
			int newx = currx + addx[i]; int newy = curry + addy[i];
			if (newx >= 0 && newx < n && newy >= 0 && newy < m && gra[newx][newy] == 'W') {
				vector<int> t; t.push_back(newx); t.push_back(newy);
				q.push(t);
			}
		}
	}
}


void solve1() {
	ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (gra[i][j] == 'W') {
				bfs(i, j);
				ans++;
			}
		}
	}
	cout << ans << endl;
}


int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> gra[i][j];
		}
	}

	//solve();
	solve1();
	return 0;
}