深度优先搜索 · 考级冲刺

深度优先搜索（DFS）是“一条路走到底，走不通再回头”的遍历方式，用递归实现最自然。它常用来遍历图、网格、树，或枚举所有可能。

以“数网格里有几块连通区域”为例：遇到一个没访问过的陆地格，就从它出发把整块连通的陆地全标记掉，块数加一：

int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};
void dfs(int x, int y) {
    vis[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx<0||ny<0||nx>=n||ny>=m) continue;      // 越界
        if (vis[nx][ny] || g[nx][ny]=='0') continue; // 访问过或是海
        dfs(nx, ny);
    }
}
// 主体: 遍历每格, 未访问的陆地就 dfs 一次, cnt++

每个格子最多访问一次，复杂度 $O (nm)$ 。

坑：一是一定要有 vis 标记防止重复访问导致死循环；二是四个方向的边界判断要写全，别越界；三是网格很大时递归可能爆栈，这种情况改用 BFS 或手写栈更稳。