BFS——小岛数量（二）

BFS——小岛数量（二）

题意解析

给你一个由 '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 都会被重新标记为 0。直到队列为空，搜索结束。

最终岛屿的数量就是我们进行广度优先搜索的次数。

代码实现

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();      //行数
        if(nr == 0)
            return 0;
        int nc = grid[0].size();   //列数

        int num_islands = 0;
        for (int r = 0; r < nr; r++){
            for(int c = 0; c < nc; c++){
                // 如果 遍历到某个位置为‘1’， 就进行广度优先搜索（BFS）
                if(grid[r][c] == '1'){
                    ++num_islands;
                    grid[r][c] = '0';
                    queue<pair<int, int>> neighbors;    //定义一个存放位置的队列
                    neighbors.push({r, c});             //放入当前的位置
                    while(!neighbors.empty()){
                        auto rc = neighbors.front();       // 取队列头
                        neighbors.pop();                    // 弹出队列头
                        int row = rc.first, col = rc.second;    
                        //对相邻位置进行判断，如果是1，就加入队列
                        if(row - 1 >= 0 && grid[row-1][col] == '1'){
                            neighbors.push({row - 1, col});
                            grid[row - 1][col] = '0';
                        }
                        if(row + 1 < nr && grid[row+1][col] == '1'){
                            neighbors.push({row + 1, col});
                            grid[row + 1][col] = '0';
                        }
                        if(col -1 >= 0 && grid[row][col -1 ] == '1'){
                            neighbors.push({row, col - 1});
                            grid[row][col - 1] = '0';
                        }
                        if (col + 1 < nc && grid[row][col+1] == '1'){
                            neighbors.push({row, col + 1});
                            grid[row][col + 1] = '0';
                        }
                    }
                }
            }
        }
        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/