Posted on by Kalkicode
Code Matrix

# Find the number of islands

The problem is to find the number of islands in a given 2D matrix. An island is a group of connected cells with a value of 1. Two cells are considered connected if they are adjacent horizontally or vertically (not diagonally).

## Example

Consider the following 2D matrix:

``````1 1 1 0 0 0 0 0 1 0
0 0 0 0 1 1 0 0 1 0
0 1 1 1 0 1 0 0 1 1
0 0 0 1 1 1 0 0 0 1
0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0 1 0
1 0 0 0 0 1 1 0 1 1
0 1 0 0 1 1 0 0 0 1
0 1 0 0 1 0 0 1 0 1
1 1 0 0 1 0 1 1 0 0``````

In this matrix, there are 6 islands.

## Idea to Solve the Problem

To find the number of islands, we can perform a Depth-First Search (DFS) on the given matrix. We will traverse each cell in the matrix, and if the cell contains a 1 and has not been visited yet, we will perform a DFS from that cell to mark all connected cells with the same island number.

## Algorithm

1. Create an auxiliary matrix of the same dimensions as the input matrix, initialized with all zeroes. This matrix will be used to mark visited cells and assign island numbers.
2. Initialize a variable `counter` to keep track of the number of islands.
3. Traverse each cell (i, j) in the input matrix: a. If the current cell contains a 1 and has not been visited (the corresponding cell in the auxiliary matrix is 0), perform a DFS from that cell to mark all connected cells with the same island number. b. Increment the `counter` by 1, as we have found a new island during the DFS.
4. Display the value of `counter`, which represents the total number of islands in the matrix.

## Pseudocode

``````count_islands(nodes, rows, cols):
Create an auxiliary matrix 'result' of size rows x cols, initialized with all zeroes
counter = 0
for i from 0 to rows-1:
for j from 0 to cols-1:
if nodes[i][j] is 1 and result[i][j] is 0:
counter = counter + 1
find_islands(nodes, result, i, j, rows, cols, counter)
print "Islands: " + counter
display(result, rows, cols)

find_islands(graph, result, r, c, rows, cols, data):
if r >= rows or c >= cols or r < 0 or c < 0:
return
if graph[r][c] is 1 and result[r][c] is 0:
result[r][c] = data
find_islands(graph, result, r, c-1, rows, cols, data)   // Left
find_islands(graph, result, r, c+1, rows, cols, data)   // Right
find_islands(graph, result, r-1, c, rows, cols, data)   // Top
find_islands(graph, result, r+1, c, rows, cols, data)   // Down
find_islands(graph, result, r-1, c-1, rows, cols, data) // Top Left
find_islands(graph, result, r+1, c-1, rows, cols, data) // Top Right
find_islands(graph, result, r-1, c+1, rows, cols, data) // Bottom Left
find_islands(graph, result, r+1, c+1, rows, cols, data) // Bottom Right

display(record, rows, cols):
for i from 0 to rows-1:
for j from 0 to cols-1:
print record[i][j]
print new line

setDefault(result, rows, cols):
for i from 0 to rows-1:
for j from 0 to cols-1:
result[i][j] = 0``````

## Code Solution

``````//C Program
//Find the number of islands
#include <stdio.h>
#define R 10
#define C 10

// Show the record elements
void display(int record[R][C])
{
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
printf("%3d", record[i][j]);
}
printf("\n");
}
}
void find_islands(int graph[R][C],int result[R][C], int row, int cols, int data)
{
if (row >= R || cols >= C || row < 0 || cols < 0)
{
return;
}
if (graph[row][cols] == 1 && result[row][cols] == 0)
{
result[row][cols] = data;
//Left
find_islands(graph,result, row, cols - 1, data);
//Right
find_islands(graph,result, row, cols + 1, data);
//Top
find_islands(graph,result, row - 1, cols, data);
//Down
find_islands(graph,result, row + 1, cols, data);
//Diagonal move
// Top left
find_islands(graph,result, row - 1, cols - 1, data);
find_islands(graph,result, row + 1, cols - 1, data);
find_islands(graph,result, row - 1, cols + 1, data);
//bottom right
find_islands(graph,result, row + 1, cols + 1, data);

}
}

// Set the initial result
void setDefault(int result[R][C])
{
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
result[i][j] = 0;
}
}
}
void count_islands(int nodes[R][C])
{
int counter = 0;

// This is Used to determine islands tag
int result[R][C];

// Set default Tag
setDefault(result);

//Define loop controlling variables
int i = 0;
int j = 0;

for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
if (nodes[i][j] == 1 && result[i][j] == 0)
{
// When get new islands
counter++;

find_islands(nodes,result, i, j, counter);
}
}
}
// Display calculated result
printf("\n  Islands : %d \n\n", counter);

display(result);
}
int main()
{

int graph[R][C] =
{
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 },
{ 0, 1, 1, 1, 0, 1, 0, 0, 1, 1 },
{ 0, 0, 0, 1, 1, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 1, 0, 1, 0 },
{ 1, 0, 0, 0, 0, 1, 1, 0, 1, 1 },
{ 0, 1, 0, 0, 1, 1, 0, 0, 0, 1 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 1, 0, 0, 1, 0, 1, 1, 0, 0 }
};
display(graph);
count_islands(graph);

return 0;
}``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0``````
``````/*
Java Program
Find the number of islands
*/
public class Islands
{

// Show the record elements
public void display(int[][] record, int rows,int cols)
{
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
System.out.print("  " + record[i][j] );
}
System.out.print("\n");
}
}
public void find_islands(int[][] graph, int[][] result, int r, int c, int rows, int cols, int data)
{
if (r >= rows || c >= cols || r < 0 || c < 0)
{
return;
}
if (graph[r][c] == 1 && result[r][c] == 0)
{
result[r][c] = data;
//Left
find_islands(graph, result, r, c - 1,rows,cols, data);
//Right
find_islands(graph, result, r, c + 1,rows,cols, data);
//Top
find_islands(graph, result, r - 1, c,rows,cols, data);
//Down
find_islands(graph, result, r + 1, c,rows,cols, data);
//Diagonal move
// Top left
find_islands(graph, result, r - 1, c - 1,rows,cols, data);
find_islands(graph, result, r + 1, c - 1,rows,cols, data);
find_islands(graph, result, r - 1, c + 1,rows,cols, data);
//bottom right
find_islands(graph, result, r + 1, c + 1,rows,cols, data);
}
}
// Set the initial result
public void setDefault(int[][] result, int rows,int cols)
{
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
result[i][j] = 0;
}
}
}
public void count_islands(int[][] nodes, int rows,int cols)
{

display(nodes,rows,cols);

int counter = 0;

// This is Used to determine islands tag
int[][] result = new int[rows][cols];

// Set default Tag
setDefault(result, rows,cols);

//Define loop controlling variables
int i = 0;
int j = 0;

for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (nodes[i][j] == 1 && result[i][j] == 0)
{
// When get new islands
counter++;
find_islands(nodes, result, i, j, rows,cols, counter);
}
}
}
// Display calculated result
System.out.print("\n Islands : " + counter + " \n\n");
display(result,rows,cols);
}
public static void main(String[] args)
{
Islands land = new Islands();

int [][]graph =
{
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 },
{ 0, 1, 1, 1, 0, 1, 0, 0, 1, 1 },
{ 0, 0, 0, 1, 1, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 1, 0, 1, 0 },
{ 1, 0, 0, 0, 0, 1, 1, 0, 1, 1 },
{ 0, 1, 0, 0, 1, 1, 0, 0, 0, 1 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 1, 0, 0, 1, 0, 1, 1, 0, 0 }
};
int rows = graph.length;
int cols = graph[0].length;

land.count_islands(graph,rows,cols);
}
}``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0``````
``````// Include header file
#include <iostream>
#define R 10
#define C 10
using namespace std;
/*
C++ Program
Find the number of islands
*/
class Islands
{
public:
// Show the record elements
void display(int record[R][C])
{
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
cout << "  " << record[i][j];
}
cout << "\n";
}
}
void find_islands(int graph[R][C], int result[R][C], int r, int c, int data)
{
if (r >= R || c >= C || r < 0 || c < 0)
{
return;
}
if (graph[r][c] == 1 && result[r][c] == 0)
{
result[r][c] = data;
//Left
this->find_islands(graph, result, r, c - 1, data);
//Right
this->find_islands(graph, result, r, c + 1, data);
//Top
this->find_islands(graph, result, r - 1, c, data);
//Down
this->find_islands(graph, result, r + 1, c, data);
//Diagonal move// Top left
this->find_islands(graph, result, r - 1, c - 1, data);
this->find_islands(graph, result, r + 1, c - 1, data);
this->find_islands(graph, result, r - 1, c + 1, data);
//bottom right
this->find_islands(graph, result, r + 1, c + 1,  data);
}
}
// Set the initial result
void setDefault(int result[R][C])
{
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
result[i][j] = 0;
}
}
}
void count_islands(int nodes[R][C])
{
this->display(nodes);
int counter = 0;
// This is Used to determine islands tag
int result[R][C];
// Set default Tag
this->setDefault(result);
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < R; ++i)
{
for (j = 0; j < C; ++j)
{
if (nodes[i][j] == 1 && result[i][j] == 0)
{
// When get new islands
counter++;
this->find_islands(nodes, result, i, j, counter);
}
}
}
// Display calculated result
cout << "\n Islands : " << counter << " \n\n";
this->display(result);
}
};
int main()
{
Islands land = Islands();
int graph[R][C] = {
{
1 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 , 0
} , {
0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 0
} , {
0 , 1 , 1 , 1 , 0 , 1 , 0 , 0 , 1 , 1
} , {
0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0 , 1
} , {
0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1
} , {
1 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0
} , {
1 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 1 , 1
} , {
0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 1
} , {
0 , 1 , 0 , 0 , 1 , 0 , 0 , 1 , 0 , 1
} , {
1 , 1 , 0 , 0 , 1 , 0 , 1 , 1 , 0 , 0
}
};

land.count_islands(graph);
return 0;
}``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0``````
``````// Include namespace system
using System;
/*
C# Program
Find the number of islands
*/
public class Islands
{
// Show the record elements
public void display(int[,] record, int rows, int cols)
{
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
Console.Write("  " + record[i,j]);
}
Console.Write("\n");
}
}
public void find_islands(int[,] graph, int[,] result, int r, int c, int rows, int cols, int data)
{
if (r >= rows || c >= cols || r < 0 || c < 0)
{
return;
}
if (graph[r,c] == 1 && result[r,c] == 0)
{
result[r,c] = data;
//Left
find_islands(graph, result, r, c - 1, rows, cols, data);
//Right
find_islands(graph, result, r, c + 1, rows, cols, data);
//Top
find_islands(graph, result, r - 1, c, rows, cols, data);
//Down
find_islands(graph, result, r + 1, c, rows, cols, data);
//Diagonal move// Top left
find_islands(graph, result, r - 1, c - 1, rows, cols, data);
find_islands(graph, result, r + 1, c - 1, rows, cols, data);
find_islands(graph, result, r - 1, c + 1, rows, cols, data);
//bottom right
find_islands(graph, result, r + 1, c + 1, rows, cols, data);
}
}
// Set the initial result
public void setDefault(int[,] result, int rows, int cols)
{
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
result[i,j] = 0;
}
}
}
public void count_islands(int[,] nodes, int rows, int cols)
{
display(nodes, rows, cols);
int counter = 0;
// This is Used to determine islands tag
int[,] result = new int[rows,cols];
// Set default Tag
setDefault(result, rows, cols);
//Define loop controlling variables
int i = 0;
int j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (nodes[i,j] == 1 && result[i,j] == 0)
{
// When get new islands
counter++;
find_islands(nodes, result, i, j, rows, cols, counter);
}
}
}
// Display calculated result
Console.Write("\n Islands : " + counter + " \n\n");
display(result, rows, cols);
}
public static void Main(String[] args)
{
Islands land = new Islands();
int[,] graph =
{
{ 1, 1, 1, 0, 0, 0, 0, 0, 1, 0 },
{ 0, 0, 0, 0, 1, 1, 0, 0, 1, 0 },
{ 0, 1, 1, 1, 0, 1, 0, 0, 1, 1 },
{ 0, 0, 0, 1, 1, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 },
{ 1, 0, 0, 0, 0, 0, 1, 0, 1, 0 },
{ 1, 0, 0, 0, 0, 1, 1, 0, 1, 1 },
{ 0, 1, 0, 0, 1, 1, 0, 0, 0, 1 },
{ 0, 1, 0, 0, 1, 0, 0, 1, 0, 1 },
{ 1, 1, 0, 0, 1, 0, 1, 1, 0, 0 }
};
int rows = graph.GetLength(0);
int cols = graph.GetLength(1);
land.count_islands(graph, rows, cols);
}
}``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0``````
``````<?php
/*
Php Program
Find the number of islands
*/
class Islands
{
// Show the record elements
public	function display( & \$record, \$rows, \$cols)
{
//Define loop controlling variables
\$i = 0;
\$j = 0;
for (\$i = 0; \$i < \$rows; ++\$i)
{
for (\$j = 0; \$j < \$cols; ++\$j)
{
echo "  ". \$record[\$i][\$j];
}
echo "\n";
}
}
public	function find_islands( & \$graph, & \$result, \$r, \$c, \$rows, \$cols, \$data)
{
if (\$r >= \$rows || \$c >= \$cols || \$r < 0 || \$c < 0)
{
return;
}
if (\$graph[\$r][\$c] == 1 && \$result[\$r][\$c] == 0)
{
\$result[\$r][\$c] = \$data;
//Left
\$this->find_islands(\$graph, \$result, \$r, \$c - 1, \$rows, \$cols, \$data);
//Right
\$this->find_islands(\$graph, \$result, \$r, \$c + 1, \$rows, \$cols, \$data);
//Top
\$this->find_islands(\$graph, \$result, \$r - 1, \$c, \$rows, \$cols, \$data);
//Down
\$this->find_islands(\$graph, \$result, \$r + 1, \$c, \$rows, \$cols, \$data);
//Diagonal move// Top left
\$this->find_islands(\$graph, \$result, \$r - 1, \$c - 1, \$rows, \$cols, \$data);
\$this->find_islands(\$graph, \$result, \$r + 1, \$c - 1, \$rows, \$cols, \$data);
\$this->find_islands(\$graph, \$result, \$r - 1, \$c + 1, \$rows, \$cols, \$data);
//bottom right
\$this->find_islands(\$graph, \$result, \$r + 1, \$c + 1, \$rows, \$cols, \$data);
}
}

public	function count_islands( & \$nodes, \$rows, \$cols)
{
\$this->display(\$nodes, \$rows, \$cols);
\$counter = 0;
// This is Used to determine islands tag
\$result = array_fill(0, \$rows, array_fill(0, \$cols, 0));

//Define loop controlling variables
\$i = 0;
\$j = 0;
for (\$i = 0; \$i < \$rows; ++\$i)
{
for (\$j = 0; \$j < \$cols; ++\$j)
{
if (\$nodes[\$i][\$j] == 1 && \$result[\$i][\$j] == 0)
{
// When get new islands
\$counter++;
\$this->find_islands(\$nodes, \$result, \$i, \$j, \$rows, \$cols, \$counter);
}
}
}
// Display calculated result
echo "\n Islands : ". \$counter ." \n\n";
\$this->display(\$result, \$rows, \$cols);
}
}

function main()
{
\$land = new Islands();
\$graph = array(
array(1, 1, 1, 0, 0, 0, 0, 0, 1, 0),
array(0, 0, 0, 0, 1, 1, 0, 0, 1, 0),
array(0, 1, 1, 1, 0, 1, 0, 0, 1, 1),
array(0, 0, 0, 1, 1, 1, 0, 0, 0, 1),
array(0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
array(1, 0, 0, 0, 0, 0, 1, 0, 1, 0),
array(1, 0, 0, 0, 0, 1, 1, 0, 1, 1),
array(0, 1, 0, 0, 1, 1, 0, 0, 0, 1),
array(0, 1, 0, 0, 1, 0, 0, 1, 0, 1),
array(1, 1, 0, 0, 1, 0, 1, 1, 0, 0));
\$rows = count(\$graph);
\$cols = count(\$graph[0]);
\$land->count_islands(\$graph, \$rows, \$cols);
}
main();``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0``````
``````/*
Node Js Program
Find the number of islands
*/
class Islands
{
// Show the record elements
display(record, rows, cols)
{
//Define loop controlling variables
var i = 0;
var j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
process.stdout.write("  " + record[i][j]);
}
process.stdout.write("\n");
}
}
find_islands(graph, result, r, c, rows, cols, data)
{
if (r >= rows || c >= cols || r < 0 || c < 0)
{
return;
}
if (graph[r][c] == 1 && result[r][c] == 0)
{
result[r][c] = data;
//Left
this.find_islands(graph, result, r, c - 1, rows, cols, data);
//Right
this.find_islands(graph, result, r, c + 1, rows, cols, data);
//Top
this.find_islands(graph, result, r - 1, c, rows, cols, data);
//Down
this.find_islands(graph, result, r + 1, c, rows, cols, data);
//Diagonal move// Top left
this.find_islands(graph, result, r - 1, c - 1, rows, cols, data);
this.find_islands(graph, result, r + 1, c - 1, rows, cols, data);
this.find_islands(graph, result, r - 1, c + 1, rows, cols, data);
//bottom right
this.find_islands(graph, result, r + 1, c + 1, rows, cols, data);
}
}
count_islands(nodes, rows, cols)
{
this.display(nodes, rows, cols);
var counter = 0;
// This is Used to determine islands tag
var result = Array(rows).fill(0).map(() => new Array(cols).fill(0));
//Define loop controlling variables
var i = 0;
var j = 0;
for (i = 0; i < rows; ++i)
{
for (j = 0; j < cols; ++j)
{
if (nodes[i][j] == 1 && result[i][j] == 0)
{
// When get new islands
counter++;
this.find_islands(nodes, result, i, j, rows, cols, counter);
}
}
}
// Display calculated result
process.stdout.write("\n Islands : " + counter + " \n\n");
this.display(result, rows, cols);
}
}

function main()
{
var land = new Islands();
var graph = [
[1, 1, 1, 0, 0, 0, 0, 0, 1, 0] ,
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0] ,
[0, 1, 1, 1, 0, 1, 0, 0, 1, 1] ,
[0, 0, 0, 1, 1, 1, 0, 0, 0, 1] ,
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] ,
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0] ,
[1, 0, 0, 0, 0, 1, 1, 0, 1, 1] ,
[0, 1, 0, 0, 1, 1, 0, 0, 0, 1] ,
[0, 1, 0, 0, 1, 0, 0, 1, 0, 1] ,
[1, 1, 0, 0, 1, 0, 1, 1, 0, 0]
];
var rows = graph.length;
var cols = graph[0].length;
land.count_islands(graph, rows, cols);
}
main();``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0``````
``````#   Python 3 Program
#   Find the number of islands

class Islands :
#  Show the record elements
def display(self, record, rows, cols) :
# Define loop controlling variables
i = 0
j = 0
while (i < rows) :
j = 0
while (j < cols) :
print("  ", record[i][j], end = "")
j += 1

print(end = "\n")
i += 1

def find_islands(self, graph, result, r, c, rows, cols, data) :
if (r >= rows or c >= cols or r < 0 or c < 0) :
return

if (graph[r][c] == 1 and result[r][c] == 0) :
result[r][c] = data
# Left
self.find_islands(graph, result, r, c - 1, rows, cols, data)
# Right
self.find_islands(graph, result, r, c + 1, rows, cols, data)
# Top
self.find_islands(graph, result, r - 1, c, rows, cols, data)
# Down
self.find_islands(graph, result, r + 1, c, rows, cols, data)
# Diagonal move// Top left
self.find_islands(graph, result, r - 1, c - 1, rows, cols, data)
self.find_islands(graph, result, r + 1, c - 1, rows, cols, data)
self.find_islands(graph, result, r - 1, c + 1, rows, cols, data)
# bottom right
self.find_islands(graph, result, r + 1, c + 1, rows, cols, data)

def count_islands(self, nodes, rows, cols) :
self.display(nodes, rows, cols)
counter = 0
#  This is Used to determine islands tag
result = [[0] * (cols) for _ in range(rows) ]
# Define loop controlling variables
i = 0
j = 0
while (i < rows) :
j = 0
while (j < cols) :
if (nodes[i][j] == 1 and result[i][j] == 0) :
#  When get new islands
counter += 1
self.find_islands(nodes, result, i, j, rows, cols, counter)

j += 1

i += 1

#  Display calculated result
print("\n Islands : ", counter ," \n")
self.display(result, rows, cols)

def main() :
land = Islands()
graph = [
[1, 1, 1, 0, 0, 0, 0, 0, 1, 0] ,
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0] ,
[0, 1, 1, 1, 0, 1, 0, 0, 1, 1] ,
[0, 0, 0, 1, 1, 1, 0, 0, 0, 1] ,
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] ,
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0] ,
[1, 0, 0, 0, 0, 1, 1, 0, 1, 1] ,
[0, 1, 0, 0, 1, 1, 0, 0, 0, 1] ,
[0, 1, 0, 0, 1, 0, 0, 1, 0, 1] ,
[1, 1, 0, 0, 1, 0, 1, 1, 0, 0]
]
rows = len(graph)
cols = len(graph[0])
land.count_islands(graph, rows, cols)

if __name__ == "__main__": main()``````

#### Output

``````   1   1   1   0   0   0   0   0   1   0
0   0   0   0   1   1   0   0   1   0
0   1   1   1   0   1   0   0   1   1
0   0   0   1   1   1   0   0   0   1
0   0   0   0   0   0   0   0   0   1
1   0   0   0   0   0   1   0   1   0
1   0   0   0   0   1   1   0   1   1
0   1   0   0   1   1   0   0   0   1
0   1   0   0   1   0   0   1   0   1
1   1   0   0   1   0   1   1   0   0

Islands :  6

1   1   1   0   0   0   0   0   2   0
0   0   0   0   3   3   0   0   2   0
0   3   3   3   0   3   0   0   2   2
0   0   0   3   3   3   0   0   0   2
0   0   0   0   0   0   0   0   0   2
4   0   0   0   0   0   5   0   2   0
4   0   0   0   0   5   5   0   2   2
0   4   0   0   5   5   0   0   0   2
0   4   0   0   5   0   0   6   0   2
4   4   0   0   5   0   6   6   0   0``````
``````#   Ruby Program
#   Find the number of islands

class Islands
#  Show the record elements
def display(record, rows, cols)
# Define loop controlling variables
i = 0
j = 0
while (i < rows)
j = 0
while (j < cols)
print("  ", record[i][j])
j += 1
end

print("\n")
i += 1
end

end

def find_islands(graph, result, r, c, rows, cols, data)
if (r >= rows || c >= cols || r < 0 || c < 0)
return
end

if (graph[r][c] == 1 && result[r][c] == 0)
result[r][c] = data
# Left
self.find_islands(graph, result, r, c - 1, rows, cols, data)
# Right
self.find_islands(graph, result, r, c + 1, rows, cols, data)
# Top
self.find_islands(graph, result, r - 1, c, rows, cols, data)
# Down
self.find_islands(graph, result, r + 1, c, rows, cols, data)
# Diagonal move// Top left
self.find_islands(graph, result, r - 1, c - 1, rows, cols, data)
self.find_islands(graph, result, r + 1, c - 1, rows, cols, data)
self.find_islands(graph, result, r - 1, c + 1, rows, cols, data)
# bottom right
self.find_islands(graph, result, r + 1, c + 1, rows, cols, data)
end

end

def count_islands(nodes, rows, cols)
self.display(nodes, rows, cols)
counter = 0
#  This is Used to determine islands tag
result = Array.new(rows) {Array.new(cols) {0}}
# Define loop controlling variables
i = 0
j = 0
while (i < rows)
j = 0
while (j < cols)
if (nodes[i][j] == 1 && result[i][j] == 0)
#  When get new islands
counter += 1
self.find_islands(nodes, result, i, j, rows, cols, counter)
end

j += 1
end

i += 1
end

#  Display calculated result
print("\n Islands : ", counter ," \n\n")
self.display(result, rows, cols)
end

end

def main()
land = Islands.new()
graph = [
[1, 1, 1, 0, 0, 0, 0, 0, 1, 0] ,
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0] ,
[0, 1, 1, 1, 0, 1, 0, 0, 1, 1] ,
[0, 0, 0, 1, 1, 1, 0, 0, 0, 1] ,
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] ,
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0] ,
[1, 0, 0, 0, 0, 1, 1, 0, 1, 1] ,
[0, 1, 0, 0, 1, 1, 0, 0, 0, 1] ,
[0, 1, 0, 0, 1, 0, 0, 1, 0, 1] ,
[1, 1, 0, 0, 1, 0, 1, 1, 0, 0]
]
rows = graph.length
cols = graph[0].length
land.count_islands(graph, rows, cols)
end

main()``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0
``````
``````/*
Scala Program
Find the number of islands
*/
class Islands
{
// Show the record elements
def display(record: Array[Array[Int]], rows: Int, cols: Int): Unit = {
//Define loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
print("  " + record(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
def find_islands(graph: Array[Array[Int]], result: Array[Array[Int]], r: Int, c: Int, rows: Int, cols: Int, data: Int): Unit = {
if (r >= rows || c >= cols || r < 0 || c < 0)
{
return;
}
if (graph(r)(c) == 1 && result(r)(c) == 0)
{
result(r)(c) = data;
//Left
this.find_islands(graph, result, r, c - 1, rows, cols, data);
//Right
this.find_islands(graph, result, r, c + 1, rows, cols, data);
//Top
this.find_islands(graph, result, r - 1, c, rows, cols, data);
//Down
this.find_islands(graph, result, r + 1, c, rows, cols, data);
//Diagonal move// Top left
this.find_islands(graph, result, r - 1, c - 1, rows, cols, data);
this.find_islands(graph, result, r + 1, c - 1, rows, cols, data);
this.find_islands(graph, result, r - 1, c + 1, rows, cols, data);
//bottom right
this.find_islands(graph, result, r + 1, c + 1, rows, cols, data);
}
}
def count_islands(nodes: Array[Array[Int]], rows: Int, cols: Int): Unit = {
this.display(nodes, rows, cols);
var counter: Int = 0;
// This is Used to determine islands tag
var result: Array[Array[Int]] = Array.fill[Int](rows, cols)(0);
//Define loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (nodes(i)(j) == 1 && result(i)(j) == 0)
{
// When get new islands
counter += 1;
this.find_islands(nodes, result, i, j, rows, cols, counter);
}
j += 1;
}
i += 1;
}
// Display calculated result
print("\n Islands : " + counter + " \n\n");
this.display(result, rows, cols);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var land: Islands = new Islands();
var graph: Array[Array[Int]] = Array(
Array(1, 1, 1, 0, 0, 0, 0, 0, 1, 0),
Array(0, 0, 0, 0, 1, 1, 0, 0, 1, 0),
Array(0, 1, 1, 1, 0, 1, 0, 0, 1, 1),
Array(0, 0, 0, 1, 1, 1, 0, 0, 0, 1),
Array(0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
Array(1, 0, 0, 0, 0, 0, 1, 0, 1, 0),
Array(1, 0, 0, 0, 0, 1, 1, 0, 1, 1),
Array(0, 1, 0, 0, 1, 1, 0, 0, 0, 1),
Array(0, 1, 0, 0, 1, 0, 0, 1, 0, 1),
Array(1, 1, 0, 0, 1, 0, 1, 1, 0, 0)
);
var rows: Int = graph.length;
var cols: Int = graph(0).length;
land.count_islands(graph, rows, cols);
}
}``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0``````
``````/*
Swift 4 Program
Find the number of islands
*/
class Islands
{
// Show the record elements
func display(_ record: [[Int]], _ rows: Int, _ cols: Int)
{
//Define loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
print("  ", record[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
func find_islands(_ graph: [[Int]], _ result: inout[[Int]], _ r: Int, _ c: Int, _ rows: Int, _ cols: Int, _ data: Int)
{
if (r >= rows || c >= cols || r < 0 || c < 0)
{
return;
}
if (graph[r][c] == 1 && result[r][c] == 0)
{
result[r][c] = data;
//Left
self.find_islands(graph, &result, r, c - 1, rows, cols, data);
//Right
self.find_islands(graph, &result, r, c + 1, rows, cols, data);
//Top
self.find_islands(graph, &result, r - 1, c, rows, cols, data);
//Down
self.find_islands(graph, &result, r + 1, c, rows, cols, data);
//Diagonal move// Top left
self.find_islands(graph, &result, r - 1, c - 1, rows, cols, data);
self.find_islands(graph, &result, r + 1, c - 1, rows, cols, data);
self.find_islands(graph, &result, r - 1, c + 1, rows, cols, data);
//bottom right
self.find_islands(graph, &result, r + 1, c + 1, rows, cols, data);
}
}
func count_islands(_ nodes: [[Int]], _ rows: Int, _ cols: Int)
{
self.display(nodes, rows, cols);
var counter: Int = 0;
// This is Used to determine islands tag
var result: [[Int]] = Array(repeating: Array(repeating: 0, count: cols), count: rows);
//Define loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i < rows)
{
j = 0;
while (j < cols)
{
if (nodes[i][j] == 1 && result[i][j] == 0)
{
// When get new islands
counter += 1;
self.find_islands(nodes, &result, i, j, rows, cols, counter);
}
j += 1;
}
i += 1;
}
// Display calculated result
print("\n Islands : ", counter ," \n");
self.display(result, rows, cols);
}
}
func main()
{
let land: Islands = Islands();
let graph: [[Int]] = [
[1, 1, 1, 0, 0, 0, 0, 0, 1, 0] ,
[0, 0, 0, 0, 1, 1, 0, 0, 1, 0] ,
[0, 1, 1, 1, 0, 1, 0, 0, 1, 1] ,
[0, 0, 0, 1, 1, 1, 0, 0, 0, 1] ,
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] ,
[1, 0, 0, 0, 0, 0, 1, 0, 1, 0] ,
[1, 0, 0, 0, 0, 1, 1, 0, 1, 1] ,
[0, 1, 0, 0, 1, 1, 0, 0, 0, 1] ,
[0, 1, 0, 0, 1, 0, 0, 1, 0, 1] ,
[1, 1, 0, 0, 1, 0, 1, 1, 0, 0]
];
let rows: Int = graph.count;
let cols: Int = graph[0].count;
land.count_islands(graph, rows, cols);
}
main();``````

#### Output

``````   1   1   1   0   0   0   0   0   1   0
0   0   0   0   1   1   0   0   1   0
0   1   1   1   0   1   0   0   1   1
0   0   0   1   1   1   0   0   0   1
0   0   0   0   0   0   0   0   0   1
1   0   0   0   0   0   1   0   1   0
1   0   0   0   0   1   1   0   1   1
0   1   0   0   1   1   0   0   0   1
0   1   0   0   1   0   0   1   0   1
1   1   0   0   1   0   1   1   0   0

Islands :  6

1   1   1   0   0   0   0   0   2   0
0   0   0   0   3   3   0   0   2   0
0   3   3   3   0   3   0   0   2   2
0   0   0   3   3   3   0   0   0   2
0   0   0   0   0   0   0   0   0   2
4   0   0   0   0   0   5   0   2   0
4   0   0   0   0   5   5   0   2   2
0   4   0   0   5   5   0   0   0   2
0   4   0   0   5   0   0   6   0   2
4   4   0   0   5   0   6   6   0   0``````
``````/*
Kotlin Program
Find the number of islands
*/
class Islands
{
// Show the record elements
fun display(record: Array<Array<Int>> , rows: Int, cols: Int): Unit
{
//Define loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i<rows)
{

while (j<cols)
{
print("  " + record[i][j]);
j += 1;
}
print("\n");
i += 1;
j = 0;
}
}
fun find_islands(graph: Array<Array<Int>> , result: Array<Array<Int>> , r: Int, c: Int, rows: Int, cols: Int, data: Int): Unit
{
if (r>= rows || c>= cols || r<0 || c<0)
{
return;
}
if (graph[r][c] == 1 && result[r][c] == 0)
{
result[r][c] = data;
//Left
this.find_islands(graph, result, r, c - 1, rows, cols, data);
//Right
this.find_islands(graph, result, r, c + 1, rows, cols, data);
//Top
this.find_islands(graph, result, r - 1, c, rows, cols, data);
//Down
this.find_islands(graph, result, r + 1, c, rows, cols, data);
//Diagonal move// Top left
this.find_islands(graph, result, r - 1, c - 1, rows, cols, data);
this.find_islands(graph, result, r + 1, c - 1, rows, cols, data);
this.find_islands(graph, result, r - 1, c + 1, rows, cols, data);
//bottom right
this.find_islands(graph, result, r + 1, c + 1, rows, cols, data);
}
}
fun count_islands(nodes: Array<Array<Int>> , rows: Int, cols: Int): Unit
{
this.display(nodes, rows, cols);
var counter: Int = 0;
// This is Used to determine islands tag
var result: Array<Array<Int>> = Array(rows)
{
Array(cols)
{
0
}
};
//Define loop controlling variables
var i: Int = 0;
var j: Int = 0;
while (i<rows)
{

while (j<cols)
{
if (nodes[i][j] == 1 && result[i][j] == 0)
{
// When get new islands
counter += 1;
this.find_islands(nodes, result, i, j, rows, cols, counter);
}
j += 1;
}
i += 1;
j = 0;
}
// Display calculated result
print("\n Islands : " + counter + " \n\n");
this.display(result, rows, cols);
}
}
fun main(args: Array<String>): Unit
{
var land: Islands = Islands();
var graph: Array<Array<Int>> = arrayOf(
arrayOf(1, 1, 1, 0, 0, 0, 0, 0, 1, 0),
arrayOf(0, 0, 0, 0, 1, 1, 0, 0, 1, 0),
arrayOf(0, 1, 1, 1, 0, 1, 0, 0, 1, 1),
arrayOf(0, 0, 0, 1, 1, 1, 0, 0, 0, 1),
arrayOf(0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
arrayOf(1, 0, 0, 0, 0, 0, 1, 0, 1, 0),
arrayOf(1, 0, 0, 0, 0, 1, 1, 0, 1, 1),
arrayOf(0, 1, 0, 0, 1, 1, 0, 0, 0, 1),
arrayOf(0, 1, 0, 0, 1, 0, 0, 1, 0, 1),
arrayOf(1, 1, 0, 0, 1, 0, 1, 1, 0, 0)
);
var rows: Int = graph.count();
var cols: Int = graph[0].count();
land.count_islands(graph, rows, cols);
}``````

#### Output

``````  1  1  1  0  0  0  0  0  1  0
0  0  0  0  1  1  0  0  1  0
0  1  1  1  0  1  0  0  1  1
0  0  0  1  1  1  0  0  0  1
0  0  0  0  0  0  0  0  0  1
1  0  0  0  0  0  1  0  1  0
1  0  0  0  0  1  1  0  1  1
0  1  0  0  1  1  0  0  0  1
0  1  0  0  1  0  0  1  0  1
1  1  0  0  1  0  1  1  0  0

Islands : 6

1  1  1  0  0  0  0  0  2  0
0  0  0  0  3  3  0  0  2  0
0  3  3  3  0  3  0  0  2  2
0  0  0  3  3  3  0  0  0  2
0  0  0  0  0  0  0  0  0  2
4  0  0  0  0  0  5  0  2  0
4  0  0  0  0  5  5  0  2  2
0  4  0  0  5  5  0  0  0  2
0  4  0  0  5  0  0  6  0  2
4  4  0  0  5  0  6  6  0  0``````

## Output Explanation

The given Java code implements the above algorithm to find the number of islands in the given 2D matrix. It prints the original matrix, the number of islands, and the matrix with each cell marked with the corresponding island number.

## Time Complexity

The time complexity of the provided solution is O(rows * cols), where 'rows' is the number of rows and 'cols' is the number of columns in the 2D matrix. The function traverses each element in the matrix once, and each operation takes constant time. Therefore, the overall time complexity is linear in the size of the matrix.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post