Home Number of Islands
Post
Cancel

LeetCode #200: Number of Islands (C/C++).

medium

source: https://leetcode.com/problems/number-of-islands
C/C++ Solution to LeetCode problem 200. Number of Islands.

Problem


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.

Examples


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

Constraints


  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

Solution


We will perform a Deep First Search:

  • Iterate through every point of the map
    • If the point is '0' then whe ignore it and move to the next one.
    • If the point is '1':
      • We mark it as '0' and increase the count of islands,
      • We explore the 4 points around it in a recursive way (DFS).
        • For every adjacent point, if it is '1' we explore it, otherwise we ignore it.

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
class Solution {
public:
  void exploreNode(vector<vector<char>>& grid, int r, int c) {
    grid[r][c] = '0';
    if (r > 0 && grid[r-1][c] == '1')  
      exploreNode(grid, r-1, c);
    if (c > 0 && grid[r][c-1] == '1')  
      exploreNode(grid, r, c-1);
    if (r<(grid.size() - 1) && grid[r+1][c] == '1')  
      exploreNode(grid, r+1, c);
    if (c<(grid[r].size() - 1) && grid[r][c+1] == '1')  
      exploreNode(grid, r, c+1);
  }

  int numIslands(vector<vector<char>>& grid) {
    int islands = 0;

    for (int r=0; r<grid.size(); r+= 1) {
      for (int c=0; c<grid[r].size(); c+=1 ) {
        if (grid[r][c] == '0') 
          continue;

        islands += 1;
        exploreNode(grid, r, c);
      }
    }

    return islands;
  }
};
This post is licensed under CC BY 4.0 by the author.

Valid Anagram

Find All Anagrams in a String