Oil Deposits HDU - 1241 (连通块个数)

发布时间 2023-03-23 15:17:02作者: HelloHeBin

题意:求连通块的数量。
分析:遍历每个点,dfs处理没有标记过的连通点,每次标记完成都是一个连通块处理完成。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 110, INF = 0x3f3f3f3f;
string s[N];
int n, m, d[][2] = {-1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1};

void dfs(int x, int y) {
    s[x][y] = '*';
    for (int i = 0; i < 8; i++) {
        int tx = x + d[i][0], ty = y + d[i][1];
        if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
        if (s[tx][ty] == '*') continue;
        dfs(tx, ty);
    }
}
int main() {
    while (cin >> n >> m && n) {
        for (int i = 0; i < n; i++) cin >> s[i];
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (s[i][j] == '@') ans++, dfs(i, j);
        cout << ans << endl;
    }
    return 0;
}