C++深搜例题代码加讲解

        题目描述：给定一个二维数组，其中 0 表示陆地，1 表示水域，求有多少个岛屿（岛屿是由一块或多块相邻的陆地组成的，相邻指上下左右四个方向）。

输入: [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 输出: 3

#include 
#include 
using namespace std;
 
int m, n; // m为行数，n为列数
vectorint>> grid; // 存储地图的二维数组
vectorbool>> visited; // 存储节点是否被访问过的二维数组
 
// 判断当前节点是否在地图中，并且没有被访问过
bool isValid(int i, int j) {
    return i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == 0 && !visited[i][j];
}
 
// 深搜遍历当前节点的上下左右四个方向
void dfs(int i, int j) {
    visited[i][j] = true;
    if (isValid(i-1, j)) dfs(i-1, j); // 上
    if (isValid(i+1, j)) dfs(i+1, j); // 下
    if (isValid(i, j-1)) dfs(i, j-1); // 左
    if (isValid(i, j+1)) dfs(i, j+1); // 右
}
 
int main() {
    // 初始化地图二维数组
    grid = {
        {1,1,0,0,0},
        {1,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,1,1},
    };
 
    // 初始化访问节点是否被访问过的二维数组
    m = grid.size();
    n = grid[0].size();
    visited = vectorbool>>(m, vector<bool>(n, false));
 
    int islandCount = 0; // 岛屿数量
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 0 && !visited[i][j]) { // 如果当前节点是陆地且未被访问过
                islandCount++; // 岛屿数量加1
                dfs(i, j); // 从当前节点开始深搜遍历
            }
        }
    }
 
    cout << "The number of islands is: " << islandCount << endl;
 
    return 0;
}

        首先定义了一个isValid函数，用来判断当前节点是否在地图中，并且没有被访问过。

        然后定义了一个dfs函数，用来深搜遍历当前节点的上下左右四个方向。在遍历之前，需要将当前节点标记为已访问。

        最后在主函数中，遍历地图的每一个节点，如果节点是陆地且未被访问过，说明是一个新的岛屿，将岛屿数量加1，并从当前节点开始深搜遍历。

        注意：在初始化visited数组时，不能使用memset，因为visited不是一个一维数组，使用memset会出现数组访问越界的问题。正确的初始化方式是使用vector来初始化visited数组。