Find the number of islands
Here given code implementation process.
//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
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.
New Comment