岛屿数量

题目链接

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

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

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

示例:

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

思路

解法一：

深度优先遍历（DFS）

解题的关键在于如何确定一个岛屿的边界以及如何进行遍历 扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。 最终岛屿的数量就是我们进行深度优先搜索的次数

  1. 遍历网格，若为1，则执行DFS,开始统计岛屿数量；
  2. 终止条件：
    • (i, j) 越过矩阵边界;
    • grid[i][j] == 0，代表此分支已越过岛屿边界。
  3. 返回 count.
#include <iostream>
#include <vector>

class Solution
{
public:
    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 (grid[i][j] == '1') // 如果是1，则开始统计岛屿数量
                {
                    dfs(grid, i, j); // 执行DFS
                    count++;
                }
            }
        }
        return count;
    }

    void dfs(vector<vector<char>>& grid, int r, int c)
    {
        if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c] == '0') {
            return;
        }
        grid[r][c] = '0'; // 将1变成0

        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
};

解法一：

广度优先遍历（BFS）

解题的关键在于如何确定一个岛屿的边界以及如何进行遍历

借用一个队列 queue，判断队列首部节点 (i, j) 是否未越界且为 1：

  • 若是则置零（删除岛屿节点），并将此节点上下左右节点 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 加入队列；
  • 若不是则跳过此节点；
  • 循环 pop 队列首节点，直到整个队列为空，此时已经遍历完此岛屿
  1. 遍历网格，若为1，则执行BFS,开始统计岛屿数量；
  2. 终止条件：
    • (i, j) 越过矩阵边界;
    • grid[i][j] == 0，代表此分支已越过岛屿边界。
  3. 返回 count.
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        int m = grid.size();
        int n = grid[0].size();
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }

    void bfs(vector<vector<char>>& grid, int i, int j) {
        queue<pair<int, int>> q;
        q.push(make_pair(i, j));

        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            int row = node.first;
            int col = node.second;

            if (row < 0 || col < 0 || row >= grid.size() || col >= grid[0].size() || grid[row][col] == '0') 
                continue;
            
            grid[row][col] = '0';
            q.push(make_pair(row + 1, col));
            q.push(make_pair(row, col + 1));
            q.push(make_pair(row, col - 1));
            q.push(make_pair(row - 1, col));

        }
    }
};