HDU 2952 Counting Sheep：DFS 連通分量計數經典入門

問題描述

n×m 網格，'*' 代表羊，'.' 代表空地。羊群定義為上下左右相連的 '*' 區域。求羊群數量。多測試用例。

DFS 洪水填充

int n, m; char grid[105][105]; bool vis[105][105];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};

void dfs(int x, int y) {
    vis[x][y] = true;
    for (int d=0; d<4; ++d) {
        int nx = x+dx[d], ny = y+dy[d];
        if (nx<0||nx>=n||ny<0||ny>=m) continue;
        if (vis[nx][ny] || grid[nx][ny]=='.') continue;
        dfs(nx, ny);
    }
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i=0;i> grid[i];
        memset(vis, 0, sizeof vis);
        int cnt = 0;
        for (int i=0;i

void bfs(int sx, int sy) {
    queue> q; q.emplace(sx,sy); vis[sx][sy]=true;
    while (!q.empty()) {
        auto [x,y] = q.front(); q.pop();
        for (int d=0; d<4; ++d) {
            int nx=x+dx[d], ny=y+dy[d];
            if (nx<0||nx>=n||ny<0||ny>=m) continue;
            if (vis[nx][ny] || grid[nx][ny]=='.') continue;
            vis[nx][ny]=true; q.emplace(nx,ny);
        }
    }
}