LeetCode-200 岛屿数量⭐

📝题目

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

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

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

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例 2:

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

📝思路

想法一：深度优先遍历DFS。

• 目标是找到矩阵中 “岛屿的数量” ，上下左右相连的 1 都被认为是连续岛屿。
• 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’，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。
• 主循环：遍历整个矩阵，当遇到 grid[i][j] == ‘1’ 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。

想法二：广度优先遍历BFS。

• 主循环和思路一类似，不同点是在于搜索某岛屿边界的方法不同。
• bfs 方法：
  • 借用一个队列 queue，判断队列首部节点 (i, j) 是否未越界且为 1：
    • 若是则置零（删除岛屿节点），并将此节点上下左右节点 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 加入队列；
    • 若不是则跳过此节点；
  • 循环 pop 队列首节点，直到整个队列为空，此时已经遍历完此岛屿。
    
    
    

📝题解

//DFS（深度优先搜索）

void dfs(vector<vector<char>>& copy, int i, int j){
    if (i < 0 || j < 0 || i >= copy.size() || j >= copy[0].size() || copy[i][j] == '0') return;
    copy[i][j] = '0';
    dfs(copy, i, j-1);
    dfs(copy, i, j+1);
    dfs(copy, i-1, j);
    dfs(copy, i+1, j);
}

int numIslands(vector<vector<char>>& grid) {
    int row_num = grid.size();
    if (row_num == 0)   return 0;
    int column_num = grid[0].size();
    int result = 0;
    vector<vector<char>>& copy = grid;
    for (int i = 0; i < row_num; ++i){
        for (int j = 0; j < column_num; ++j){
            if (grid[i][j] == '1'){
                dfs(copy, i, j);
                ++result;
            }
        }
    }
    return result;
}

//BFS（广度优先搜索）

void bfs(vector<vector<char>>& grid, int i, int j){
    queue<vector<int>> q;
    q.push({i, j});
    while (!q.empty()){
        vector<int> first = q.front();
        q.pop();
        i = first[0];
        j = first[1];
        if (i >= 0 && j >= 0 && i < grid.size() && j < grid[0].size() && grid[i][j] == '1'){
            grid[i][j] = '0';
            q.push({i, j-1});
            q.push({i, j+1});
            q.push({i-1, j});
            q.push({i+1, j});
        }
    }
    return;
}
int numIslands(vector<vector<char>>& grid) {
    int row_nums = grid.size();
    if (row_nums == 0)  return 0;
    int column_nums = grid[0].size();
    int result = 0;
    
    for (int i = 0; i < row_nums; ++i){
        for (int j = 0; j < column_nums; ++j){
            if (grid[i][j] == '1'){
                bfs(grid, i, j);
                ++result;
            }
        }
    }
    return result;
}