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.
- For every adjacent point, if it is
- We mark it as
- If the point is
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;
}
};