C++递归算法处理岛屿问题详解

什么是岛屿问题？

岛屿问题是指在一个由字母 O 和 X 组成的二维矩阵中，连成一片的 O 组成的区域被称为一个岛屿。请编写一个 C++ 程序，计算出给定的矩阵中岛屿的数量。

解题思路

解题的基本思路是对每个位置进行深度优先搜索，将和当前位置连通的所有 O 都标记为已访问。如此定义岛屿的个数即为进行深度优先搜索的次数。

接下来让我们来详细分析算法实现：

1. 递归实现深度优先搜索

void dfs(vector<vector<char>>& grid, int i, int j){
    int m = grid.size(); //求出矩阵的行数
    int n = grid[0].size();  //求出矩阵的列数

    if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] != 'O') return;  //边界判断，如果当前位置越界，或者当前位置不为'O'，则退出递归

    grid[i][j] = 'X';  //标记当前位置为已访问
    dfs(grid, i-1, j);  //上
    dfs(grid, i+1, j);  //下
    dfs(grid, i, j-1);  //左
    dfs(grid, i, j+1);  //右
}

2. 对每个位置进行深度优先搜索

int numIslands(vector<vector<char>>& grid) {
    int count = 0;  //初始化岛屿计数器
    for(int i = 0;i < grid.size();i++){
        for(int j = 0;j < grid[0].size();j++){
            if(grid[i][j] == 'O'){  //如果当前位置为'O'，说明可能是岛屿的一部分
                count++;  //岛屿计数器加一
                dfs(grid, i, j);  //对当前位置进行深度优先搜索
            }
        }
    }
    return count;  //返回岛屿的个数
}

示例说明

示例1：

//输入：
[
  ['O', 'O', 'O', 'O', 'X'],
  ['O', 'O', 'X', 'O', 'O'],
  ['O', 'O', 'X', 'X', 'X'],
  ['X', 'X', 'O', 'O', 'X'],
]

//输出：
2

示例2：

//输入：
[
  ['O', 'O', 'O', 'O', 'X'],
  ['O', 'O', 'X', 'X', 'O'],
  ['O', 'O', 'X', 'X', 'X'],
  ['X', 'X', 'O', 'O', 'X'],
]

//输出：
1

以上就是本次分享的 C++ 递归算法处理岛屿问题的完整攻略。