Lake Counting题解

解题思路:

遇到第一个W时，不断用"."替换掉周围的“W”。一次DFS后，和这个W 相连的W被全部替换掉，此时次数+1；

参考代码:

#include"iostream"
using namespace std;
int n, m;
char a[1111][1111];
int ans = 0;
void dfs(int x, int y) {
	a[x][y] = '.';
	for (int i = -1;i <= 1;i++) {
		for (int j = -1;j <= 1;j++) {
			int dx = x + i;
			int dy = y + j;
			if (dx >= 0 && dx < n && dy >= 0 && dy < m && a[dx][dy] == 'W')
				dfs(dx, dy);
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < m;j++) {
			if (a[i][j] == 'W') {
				dfs(i, j);
				ans++;
			}
		}
	}
	cout << ans;
	return 0;
}