Number of Islands

Posted on Edited on In Views:

Problems like "given an 2D binary grid grid which represents a map of land and water, return the number of islands, an island is XXXX".

  • 200. Number of Islandsopen
  • 1020. Number of Enclavesopen
  • 1254. Number of Closed Islands
  • 1905. Count Sub Islandsopen
  • 695. Max Area of Island

Ref: labuladong 题解

Number of Islands

200. Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

1
2
3
4
5
6
7
Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

1
2
3
4
5
6
7
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Solution

岛屿问题的关键是"如何寻找岛屿", 这统统可以用DFS解决.

比如说题目给你输入下面这个 grid 有四片岛屿，算法应该返回 4：

img

记岛屿数量为int cnt. 我们的做法是: 每遇到一块新的陆地(land), 就将其标记为一个岛屿(cnt++), 然后对这个陆地进行DFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int numIslands(char[][] grid) {
        int M = grid.length, N = grid[0].length;

        int cnt = 0;
        for(int row = 0; row < M; row++)
            for(int col = 0; col < N; col++)
            {
                if(isLand(grid[row][col]))
                {
                    cnt++;
                    dfs_and_mark(row,col, grid);
                }
            }
        return cnt;

    }

DFS的迭代项是该岛屿四周的方格, 每当DFS遇到一个land, 就把它淹没, 变成water. 这样一来, 对每个新land的DFS都能完全消除掉一个岛屿:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void dfs_and_mark(int row, int col, char[][] grid)
    {
        int M = grid.length, N = grid[0].length;

        if(isLand(grid[row][col]))
        {
            flood(row,col,grid);//Turn this land into water.
            
            //Then apply this method to surrounding grid. Notice the limit of grid's boundary
            if(row>=1) dfs_and_mark(row-1,col,grid);
            if(row <= M-2) dfs_and_mark(row+1,col,grid);
            if(col>=1) dfs_and_mark(row,col-1,grid);
            if(col <= N-2) dfs_and_mark(row,col+1,grid);
        }
    }

Code

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
42
public int numIslands(char[][] grid) {
        int M = grid.length, N = grid[0].length;

        int cnt = 0;
        for(int row = 0; row < M; row++)
            for(int col = 0; col < N; col++)
            {
                if(isLand(grid[row][col]))
                {
                    cnt++;
                    dfs_and_mark(row,col, grid);
                }
            }
        return cnt;

    }

    private boolean isLand(char ch)
    {
        return ch == '1';
    }

    private void flood(int row, int col, char[][] grid)
    {
        grid[row][col] = '0';
    }

    private void dfs_and_mark(int row, int col, char[][] grid)
    {
        int M = grid.length, N = grid[0].length;

        if(isLand(grid[row][col]))
        {
            flood(row,col,grid);//Turn this land into water.

            //Then apply this method to surrounding grid. Notice the limit of grid's boundary
            if(row>=1) dfs_and_mark(row-1,col,grid);
            if(row <= M-2) dfs_and_mark(row+1,col,grid);
            if(col>=1) dfs_and_mark(row,col-1,grid);
            if(col <= N-2) dfs_and_mark(row,col+1,grid);
        }
    }