题目链接

Lake Counting POJ - 2386

思路

dfs也可以bfs也可以并查集

时间复杂度

$$ O(NM) $$

代码

#include <cstdio>

using namespace std;

const int MAXN = 105;

int n, m;
char s[MAXN][MAXN];

bool check(int x, int y) {
    if (1 <= x && x <= n && 1 <= y && y <= m && s[x][y] == 'W') {
        return true;
    } else {
        return false;
    }
}

void dfs(int x, int y) {
    s[x][y] = '.';
    for (int i = -1; i <= 1; i++) {
        for (int j = -1; j <= 1; j++) {
            int xx = x + i;
            int yy = y + j;
            if (check(xx, yy)) {
                dfs(xx, yy);
            }
        }
    }

}

int main() {

    scanf("%d%d", &n, &m);// don't forget &
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);// no &
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i][j] == 'W') {
                ans++;
                dfs(i, j);
            }
        }
    }
    printf("%d", ans);

    return 0;
}