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