# Number of Islands

Given a 2D grid consisting of either ` '1' ` or ` '0' ` character at each position. ` '1' ` represents land and ` '0' ` represents water. An island is a mass of land which is surrounded by water. Count the number of islands.

.

#### Example Test Cases

##### Sample Test Case 1

Input grid: ``` 11110 11010 11000 00000 ```
Expected Output: ` 1 `
Explanation: There is only one island starting at position ` (0, 0) `, since this island will be composed of every land available in the grid.

##### Sample Test Case 2

Input grid: ``` 11000 11000 00100 00011```
Expected Output: ` 3 `
Explanation: There are three islands: starting at position ` (0, 0) ` ,` (2, 2) ` and ` (3, 3)` respectively.

#### Solution

If we imagine this 2d grid in the form of a graph, then it means that the answer to this problem is the number of connected components within the graph. We can easily find the number of connected components by applying DFS through the grid as shown below

Implementation

```#include <iostream>
#include <vector>
using namespace std;

// This method starts the DFS process from position (x, y).
void dfs(int x, int y, vector<vector<char>>& grid, vector<vector<bool>>& visited) {
// Only visit the position (x, y) if it has not been visited before.
if (visited[x][y] == false) {
visited[x][y] = true;
for(int i = -1; i <= 1; i++) {
for(int j = -1; j <= 1; j++) {
// Since, we only want to traverse in horizontal and vertical direction.
if (abs(i) + abs(j) != 1) continue;

// To make sure that we don't go out of the grid.
if (x + i < 0 || x + i >= grid.size() || y + j < 0 || y + j >= grid[x].size()) continue;

// Don't visit a position which has water.
if (grid[x + i][y + j] == '0') continue;

dfs(x + i, y + j, grid, visited);
}
}
}
}

int main() {
vector<vector<char>> grid = { {'1', '1', '1', '0' }, { '0', '0', '0', '1' } };
int n = grid.size();
vector<vector<bool>> visited(n);
for(int i = 0; i < n; i++) {
for(int j = 0; j < grid[i].size(); j++) {
visited[i].push_back(false);
}
}

int noOfIslands = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < grid[i].size(); j++) {
if (visited[i][j] == false && grid[i][j] == '1') {
dfs(i, j, grid, visited);
noOfIslands++;
}
}
}

cout << "No of islands are " << noOfIslands << "\n";
}
view raw
noOfIslands.cpp hosted with ❤ by GitHub
```
Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]