搜索练习一

练第一道：给一张只含 0 和 1 的地图，数出有几片相连的 1（连通块）。深搜广搜都能做，这里用深搜，短小好写：

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

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 (g[nx][ny] == 1 && !vis[nx][ny]) dfs(nx, ny);
    }
}
// 主函数：遇到未访问的 1 就 cnt++，再 dfs 把整片标记

每个格子只访问一次，复杂度 $O(nm)$。地图特别大时递归可能过深，可改用广搜。