深度优先搜索

深度优先搜索算法（Depth First Search）：英文缩写为 DFS，是一种用于搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。深度优先搜索采用了回溯思想，该算法沿着树的深度遍历树的节点，会尽可能深的搜索树的分支。

• 回溯：会搜出每一种可能的路线（求路径，通常N<20）
• 不回溯：会搜出每一个能走的点（求能否到达）

char mp[N][N];  // 地图
bool mp[N][N];  // 到过位置的标记
int dir[4][2] = {  // 方向数组  根据需求确定搜索方向
    0, 1,
    0, -1,
    1, 0,
    -1, 0
}

void dfs(int x, int y) {  // 当前访问的点是(x, y)
    if (x, y) 是终点 {  // 遇到结束条件，如果没有结束条件就把能搜的点都搜完
        // 遇到终点做一些事情，比如打印路径、路径数、判断能否到达终点
        return;  // 返回
    }

    vis[x][y] = true;  // 标记此点被访问
    for(int i = 0; i < 4; i++) {  // 分别搜索四个方向
        int nx = x + dir[i][0];  // 下一个点的x坐标
        int ny = y + dir[i][1];  // 下一个点的y坐标
        // 如果下一个点越界了 不能走
        // 注意下面两个if要先判断是否越界，才可以访问 
        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        // 如果下一个点是障碍 或者 下一个点访问过 不能走
        if(mp[nx][ny] 是障碍 || vis[nx][ny]) continue; 
        dfs(nx, ny);  // 开始搜索下一个合法的节点
    }
    // 这个点的上下左右都搜完了，回溯到上一个节点，此点标记为未访问
    vis[x][y] = false;  // 根据需求选择是否要回溯
    // 回溯 会搜出每一种可能的路线
    // 不回溯 会搜出每一个能走的点
}

// 记录路径
int path[N * N][2];
int pathsize;

void dfs(int x, int y) {
    if 终点 {
        for(int i = 0; i < pathsize; i++) {
            printf("(%d, %d)->", path[i][0], path[i][1]);
        }
        cout << 终点 << endl;
    }
    
    vis[x][y] = true;
    path[pathsize][0] = x;  // 添加路径
    path[pathsize++][1] = y;
    
    for() 搜索下一个点
    
    vis[x][y] = false;
    pathsize--;  // 删除路径
}

对于连通块问题，可以在main函数中遍历地图，遇到能构成连通块的符号即可进入dfs，对于进入dfs的点，将其设置为不可构成连通块的符号，并不断搜索其周边连通的符号。在main函数中每次进入dfs相当于遇到一个新的连通块并标记，可以进行计数。