HDOJ 2952 Counting Sheep：网格连通分量计数 DFS

题目大意

H×W 网格（≤100×100），# 表示羊，. 表示草。上下左右相邻的羊属于同一群。求羊群数量。

DFS/BFS 标记连通分量

#include 
#include 
#include 
#include 
using namespace std;

const int N = 105;
string grid[N];
int H, W, vis[N][N];
int dx[4] = {0,0,1,-1}, dy[4] = {1,-1,0,0};

void dfs(int x, int y) {
    vis[x][y] = 1;
    for (int d = 0; d < 4; ++d) {
        int nx = x + dx[d], ny = y + dy[d];
        if (nx>=0 && nx=0 && ny> T;
    while (T--) {
        cin >> H >> W;
        for (int i = 0; i < H; ++i) cin >> grid[i];
        memset(vis, 0, sizeof(vis));
        int cnt = 0;
        for (int i = 0; i < H; ++i)
            for (int j = 0; j < W; ++j)
                if (!vis[i][j] && grid[i][j]=='#') {
                    ++cnt;
                    dfs(i, j);
                }
        cout << cnt << endl;
    }
    return 0;
}

复杂度

• 时间：O(H×W) 每格访问一次
• 空间：O(H×W) 访问标记数组 + 递归栈

关键点

1. 四向连通：仅上下左右，非八向
2. 递归深度：≤10000，栈安全；或用显式栈/队列 BFS
3. 多测试用例：每用例重置 vis 数组