DFS——小岛数量（一）

DFS——小岛数量（一）

题意解析

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:

[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]

输出: 1

示例 2:

输入:

[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]

输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

解题思路

深度优先遍历 1.遍历整个数组，遇到1，num_islands++，num_islands是记录岛的个数的 2.运行一下dfs函数，把这个岛所有陆地给我沉喽，这个岛全部的1变成0 3.等把grid全遍历完，grid就全是0了，再把num_islands输出，这个num_islands就是我们记录的岛的个数 注意：grid竟然是char类型的，所有1和0都要加单引号哦

代码实现

#include<iostream> 
#include<vector>
using namespace std;
// 深度优先搜索，其中 row,col对应递归所到的位置
void dfs(vector<vector<char>> &grid, int row, int col)
{
    int rowsize = grid.size();
    int colsize = grid[0].size();

    grid[row][col] = '0'; //用以标记已经判断过
    if (row - 1 >= 0 && grid[row - 1][col] == '1')
        dfs(grid, row - 1, col);
    if (row + 1 < rowsize && grid[row + 1][col] == '1')
        dfs(grid, row + 1, col);
    if (col - 1 >= 0 && grid[row][col - 1] == '1')
        dfs(grid, row, col - 1);
    if (col + 1 < colsize && grid[row][col + 1] == '1')
        dfs(grid, row, col + 1);
    }

int numIslands(vector<vector<char>>& grid) {
    int rowsize = grid.size();
    if(rowsize == 0)
        return 0;
    int colsize = grid[0].size();
    
    int num_islands = 0;
    for (int r = 0; r< rowsize; r++){
        for(int c = 0; c< colsize; c++){
            if(grid[r][c] == '1'){
                ++num_islands; //发现1， 岛屿数量+1 ， 并且把岛屿所有的地方通过深度搜索遍历出来
                dfs(grid, r, c);
            }
        }
    }   
         return num_islands;
} 

int main(){
    vector<vector<char> > grid;
    int row;
    int col;
    cin >> row >> col;
    
    for (int r = 0; r < row; ++r){
        vector<char> temp;
        for (int c = 0; c < col; ++c){
            char num;
            cin >> num;
            temp.push_back(num);
        }
        grid.push_back(temp);
    }
    

    cout << "岛屿数量为" << numIslands(grid);
}

参考资料

[1]https://leetcode-cn.com/problems/number-of-islands

[2]https://leetcode-cn.com/problems/number-of-islands/solution/po-shi-wu-hua-de-shen-du-you-xian-bian-li-by-shang/