Leetcode200. 岛屿数量图

题目描述

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

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

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

示例 1：

1
2
3
4
5
6
7
输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

1
2
3
4
5
6
7
输入：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'

解题思路

这道题主要考察对DFS的掌握。

这道题中如果陆地能相连，也就是上下左右位如果为’1’，那么就属于一个岛屿，那么我们就需要遍历所有的位置，根据未经访问的陆地点的数量来判断到底有多少个岛屿。对于每一个位置，我们都需要访问同属于一个岛屿的位置。我们可以使用一个visited数组来记录该陆地是否被访问过，如果该陆地已经被访问过，就打上标记，来避免不必要的重复。

那么我们的一个重点就是对于每一个点，如果递归的标记同属于一个岛屿的陆地。这时候我们需要借鉴一下对树的遍历方法。 首先，需要定义递归的出口。在树的遍历中，结点为空为出口；那么，我们可以定义所访问的点(i,j)不在grid中时为出口。在树的遍历中，我们需要依次遍历树的左右结点；那么，在这道题中，我们就需要遍历(i,j)点的上下左右四个位置。

根据算法思路，我们可以得到相应的代码。

**PS：**这道题也可以通过并查集来进行求解，但是DFS的方法更为常用。

示例代码

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
void DFS(vector<vector<char>>&grid,vector<vector<bool>>&visited,int i,int j)
{
    if(i<0||j<0||i>=grid.size()||j>=grid[0].size()) return;
    if(grid[i][j]=='1'&&visited[i][j]==false)
    {
        visited[i][j]=true;
        DFS(grid,visited,i-1,j);
        DFS(grid,visited,i+1,j);
        DFS(grid,visited,i,j-1);
        DFS(grid,visited,i,j+1);
    }
}

int numIslands(vector<vector<char>>& grid)
{
    vector<vector<bool>>visited(grid.size(),vector<bool>(grid[0].size(),false));
    int res=0;
    for(int i=0;i<grid.size();++i)
    {
        for(int j=0;j<grid[0].size();++j)
        {
            if(!visited[i][j]&&grid[i][j]=='1') res++;
            DFS(grid,visited,i,j);
        }
    }
    return res;
}