LeetCode：200. 岛屿数量

200. 岛屿数量

给你一个由 '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
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

链接：https://leetcode-cn.com/problems/number-of-islands

 

思路：

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

时间复杂度：O(m * n)  最坏情况，都是陆地，遍历二维数组每个节点

空间复杂度：O(m * n)  最坏情况，都是陆地，遍历二维数组每个节点

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

void dfs(vector<vector<char>>& grid,  int i, int j)
{
    // 左右上下
    if (i < 0 || j < 0 || i >= grid.size() || j >= grid[i].size() || grid[i][j] == '0')
        return; 

    grid[i][j] = '0';       // 将当前的值设为0，表示已经遍历过，标记以避免重复遍历
    dfs(grid, i - 1, j);
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}