LeetCode 刷题 [C++] 第200题. 岛屿数量 (广度优先遍历BFS与深度优先遍历DFS)_c++广度优先搜索孤岛问题

题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例 1：
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：
输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：
    m == grid.length
    n == grid[i].length
    1 <= m, n <= 300
    grid[i][j] 的值为 '0' 或 '1'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

广度优先遍历 BFS

题目是找到矩阵中 “岛屿的数量” ，因此上下左右相连的’1’都被认为是同一个连续的岛屿。
1.主循环：遍历整个矩阵，当遇到 grid[i][j] == ‘1’ 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。
2.bfs方法：借用一个队列queue，将未越界且为字符’1’的节点 (i, j)加入队列：

• 弹出队列首节点，并将此节点上下左右节点 (i+1,j),(i-1,j),(i,j+1),(i,j-1)中未越界且为字符’1’的加入队列；
• 若其上下左右节点不符合条件，则不进行任何操作，继续弹出队列首元素节点;
• 循环pop队列首节点，直到整个队列为空，此时已经遍历完当前岛屿。

具体实现代码如下：

class Solution {
public:
    void bfs(vector<vector<char>>& grid,int i,int j,int cow,int col) {
        queue<vector<int>> curQue;
        curQue.emplace(vector<int>{i,j});
        while(!curQue.empty()) {
            auto curNode = curQue.front();
            curQue.pop();
            int m=curNode[0],n=curNode[1];
            if(m-1>=0 && grid[m-1][n] == '1') {
                grid[m-1][n] = '0';
                curQue.emplace(vector<int>{m-1,n});
            }
            if(m+1<cow && grid[m+1][n] == '1') {
                grid[m+1][n] = '0';
                curQue.emplace(vector<int>{m+1,n});
            }
            if(n-1>=0 && grid[m][n-1] == '1') {
                grid[m][n-1] = '0';
                curQue.emplace(vector<int>{m,n-1});
            }
            if(n+1<col && grid[m][n+1] == '1') {
                grid[m][n+1] = '0';
                curQue.emplace(vector<int>{m,n+1});
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        int count=0,cow=grid.size(),col=grid[0].size();
        for(int i=0;i<cow;++i) {
            for(int j=0;j<col;++j) {
                if('1' == grid[i][j]) {
                    grid[i][j] = '0';
                    bfs(grid,i,j,cow,col);
                    ++count;
                }
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

AC结果：

深度优先遍历DFS

1.主循环：遍历整个矩阵，当遇到 grid[i][j] == ‘1’ 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。
2.dfs方法： 设目前指针指向一个岛屿中的某一点 (i, j)，寻找包括此点的岛屿边界。

• 从 (i, j) 向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索。
• 终止条件：(i, j) 越过矩阵边界; grid[i][j] == ‘0’，代表此分支已越过岛屿边界。
• 搜索岛屿的同时，执行 grid[i][j] = ‘0’，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。

具体实现代码如下：

class Solution {
public:
    void dfs(vector<vector<char>>& grid,int i,int j) {
        if(i<0 || i>=grid.size() || j<0 || j>=grid[i].size() || grid[i][j]=='0' ) return;
        grid[i][j]='0';
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
    }
    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (nr == 0) return 0;
        int nc = grid[0].size();

        int count=0;
        for(int i=0;i<nr;++i) {
            for(int j=0;j<nc;++j) {
                if('1' == grid[i][j]) {
                    dfs(grid,i,j);
                    ++count;
                }
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

AC结果：