Red and Black HDU - 1312 (连通块的大小)

发布时间 2023-03-23 15:52:40作者: 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, 0, 0, 1, 1, 0, 0, -1};
int ans = 0;
void dfs(int x, int y) {
    ans++, s[x][y] = '*';
    for (int i = 0; i < 4; 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 >> m >> n && n) {
        for (int i = 0; i < n; i++) cin >> s[i];
        ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (s[i][j] == '@') dfs(i, j);
        cout << ans << endl;
    }
    return 0;
}