Algorithm Puzzles: Number of Islands

Posted on Edited on In Views: Word count in article: 232 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Number of Islands

Puzzle

Puzzle from leetcode:

Given an m x n 2d grid 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Example 1:

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:

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

It looks like a typical depth-first search puzzle:

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
class Solution {
  public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0) return 0;

        mSize = grid.size();
        nSize = grid[0].size();

        int island = 0;

        for (int m = 0; m < mSize; ++m) {
            for (int n = 0; n < nSize; ++n) {
                if (grid[m][n] == '0') {
                    continue;
                } else {
                    bfs(grid, m, n);
                    ++island;
                }
            }
        }

        return island;
    }

  private:
    int mSize;
    int nSize;
    void bfs(vector<vector<char>>& grid, int m, int n) {
        if (m < 0 || n < 0 || m >= mSize || n >= nSize || grid[m][n] != '1')
            return;

        grid[m][n] = '0';
        bfs(grid, m + 1, n);
        bfs(grid, m - 1, n);
        bfs(grid, m, n + 1);
        bfs(grid, m, n - 1);
    }
};