Dada una array booleana 2D, encuentre el número de islas. Un grupo de unos conectados forma una isla. Por ejemplo, la siguiente array contiene 5 islas
Ejemplo:
Input : mat[][] = {{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}}
Output : 5
Esta es una variación del problema estándar: «Contar el número de componentes conectados en un gráfico no dirigido».
Antes de pasar al problema, comprendamos qué es un componente conexo. Un componente conexo de un grafo no dirigido es un subgrafo en el que cada dos vértices están conectados entre sí por un camino o caminos, y que no está conectado a ningún otro vértice fuera del subgrafo.
Por ejemplo, el gráfico que se muestra a continuación tiene tres componentes conectados.
Un gráfico donde todos los vértices están conectados entre sí tiene exactamente un componente conectado, que consiste en todo el gráfico. Un gráfico de este tipo con un solo componente conexo se denomina gráfico fuertemente conexo.
El problema se puede resolver fácilmente aplicando DFS() en cada componente. En cada llamada a DFS(), se visita un componente o un subgráfico. Llamaremos a DFS en el siguiente componente no visitado. El número de llamadas a DFS() da el número de componentes conectados. También se puede utilizar BFS.
¿Qué es una isla?
Un grupo de unos conectados forma una isla. Por ejemplo, la siguiente array contiene 4 islas
Una celda en array 2D se puede conectar a 8 vecinos. Entonces, a diferencia del DFS() estándar, donde recursivamente llamamos a todos los vértices adyacentes, aquí podemos llamar recursivamente solo a 8 vecinos. Realizamos un seguimiento de los 1 visitados para que no se vuelvan a visitar.
C++
// C++ Program to count islands in boolean 2D matrix
#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5
// A function to check if a given
// cell (row, col) can be included in DFS
int isSafe(int M[][COL], int row, int col,
bool visited[][COL])
{
// row number is in range, column
// number is in range and value is 1
// and not yet visited
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] && !visited[row][col]);
}
// A utility function to do DFS for a
// 2D boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS(int M[][COL], int row, int col,
bool visited[][COL])
{
// These arrays are used to get
// row and column numbers of 8
// neighbours of a given cell
static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
// Mark this cell as visited
visited[row][col] = true;
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k], col + colNbr[k], visited);
}
// The main function that returns
// count of islands in a given boolean
// 2D matrix
int countIslands(int M[][COL])
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
bool visited[ROW][COL];
memset(visited, 0, sizeof(visited));
// Initialize count as 0 and
// traverse through the all cells of
// given matrix
int count = 0;
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
// If a cell with value 1 is not
if (M[i][j] && !visited[i][j]) {
// visited yet, then new island found
// Visit all cells in this island.
DFS(M, i, j, visited);
// and increment island count
++count;
}
return count;
}
// Driver code
int main()
{
int M[][COL] = { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 } };
cout << "Number of islands is: " << countIslands(M);
return 0;
}
// This is code is contributed by rathbhupendra
C
// Program to count islands in boolean 2D matrix
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
#define ROW 5
#define COL 5
// A function to check if a given cell (row, col) can be included in DFS
int isSafe(int M[][COL], int row, int col, bool visited[][COL])
{
// row number is in range, column number is in range and value is 1
// and not yet visited
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] && !visited[row][col]);
}
// A utility function to do DFS for a 2D boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS(int M[][COL], int row, int col, bool visited[][COL])
{
// These arrays are used to get row and column numbers of 8 neighbours
// of a given cell
static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
// Mark this cell as visited
visited[row][col] = true;
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k], col + colNbr[k], visited);
}
// The main function that returns count of islands in a given boolean
// 2D matrix
int countIslands(int M[][COL])
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
bool visited[ROW][COL];
memset(visited, 0, sizeof(visited));
// Initialize count as 0 and traverse through the all cells of
// given matrix
int count = 0;
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (M[i][j] && !visited[i][j]) // If a cell with value 1 is not
{ // visited yet, then new island found
DFS(M, i, j, visited); // Visit all cells in this island.
++count; // and increment island count
}
return count;
}
// Driver program to test above function
int main()
{
int M[][COL] = { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 } };
printf("Number of islands is: %d\n", countIslands(M));
return 0;
}
Java
// Java program to count islands in boolean 2D matrix
import java.util.*;
import java.lang.*;
import java.io.*;
class Islands {
// No of rows and columns
static final int ROW = 5, COL = 5;
// A function to check if a given cell (row, col) can
// be included in DFS
boolean isSafe(int M[][], int row, int col,
boolean visited[][])
{
// row number is in range, column number is in range
// and value is 1 and not yet visited
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
}
// A utility function to do DFS for a 2D boolean matrix.
// It only considers the 8 neighbors as adjacent vertices
void DFS(int M[][], int row, int col, boolean visited[][])
{
// These arrays are used to get row and column numbers
// of 8 neighbors of a given cell
int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
// Mark this cell as visited
visited[row][col] = true;
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k], col + colNbr[k], visited);
}
// The main function that returns count of islands in a given
// boolean 2D matrix
int countIslands(int M[][])
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
boolean visited[][] = new boolean[ROW][COL];
// Initialize count as 0 and traverse through the all cells
// of given matrix
int count = 0;
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (M[i][j] == 1 && !visited[i][j]) // If a cell with
{ // value 1 is not
// visited yet, then new island found, Visit all
// cells in this island and increment island count
DFS(M, i, j, visited);
++count;
}
return count;
}
// Driver method
public static void main(String[] args) throws java.lang.Exception
{
int M[][] = new int[][] { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 } };
Islands I = new Islands();
System.out.println("Number of islands is: " + I.countIslands(M));
}
} // Contributed by Aakash Hasija
Python3
# Program to count islands in boolean 2D matrix
class Graph:
def __init__(self, row, col, g):
self.ROW = row
self.COL = col
self.graph = g
# A function to check if a given cell
# (row, col) can be included in DFS
def isSafe(self, i, j, visited):
# row number is in range, column number
# is in range and value is 1
# and not yet visited
return (i >= 0 and i < self.ROW and
j >= 0 and j < self.COL and
not visited[i][j] and self.graph[i][j])
# A utility function to do DFS for a 2D
# boolean matrix. It only considers
# the 8 neighbours as adjacent vertices
def DFS(self, i, j, visited):
# These arrays are used to get row and
# column numbers of 8 neighbours
# of a given cell
rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1];
colNbr = [-1, 0, 1, -1, 1, -1, 0, 1];
# Mark this cell as visited
visited[i][j] = True
# Recur for all connected neighbours
for k in range(8):
if self.isSafe(i + rowNbr[k], j + colNbr[k], visited):
self.DFS(i + rowNbr[k], j + colNbr[k], visited)
# The main function that returns
# count of islands in a given boolean
# 2D matrix
def countIslands(self):
# Make a bool array to mark visited cells.
# Initially all cells are unvisited
visited = [[False for j in range(self.COL)]for i in range(self.ROW)]
# Initialize count as 0 and traverse
# through the all cells of
# given matrix
count = 0
for i in range(self.ROW):
for j in range(self.COL):
# If a cell with value 1 is not visited yet,
# then new island found
if visited[i][j] == False and self.graph[i][j] == 1:
# Visit all cells in this island
# and increment island count
self.DFS(i, j, visited)
count += 1
return count
graph = [[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]]
row = len(graph)
col = len(graph[0])
g = Graph(row, col, graph)
print ("Number of islands is:")
print (g.countIslands())
# This code is contributed by Neelam Yadav
C#
// C# program to count
// islands in boolean
// 2D matrix
using System;
class GFG {
// No of rows
// and columns
static int ROW = 5, COL = 5;
// A function to check if
// a given cell (row, col)
// can be included in DFS
static bool isSafe(int[, ] M, int row,
int col, bool[, ] visited)
{
// row number is in range,
// column number is in range
// and value is 1 and not
// yet visited
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row, col] == 1 && !visited[row, col]);
}
// A utility function to do
// DFS for a 2D boolean matrix.
// It only considers the 8
// neighbors as adjacent vertices
static void DFS(int[, ] M, int row,
int col, bool[, ] visited)
{
// These arrays are used to
// get row and column numbers
// of 8 neighbors of a given cell
int[] rowNbr = new int[] { -1, -1, -1, 0,
0, 1, 1, 1 };
int[] colNbr = new int[] { -1, 0, 1, -1,
1, -1, 0, 1 };
// Mark this cell
// as visited
visited[row, col] = true;
// Recur for all
// connected neighbours
for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k],
col + colNbr[k], visited);
}
// The main function that
// returns count of islands
// in a given boolean 2D matrix
static int countIslands(int[, ] M)
{
// Make a bool array to
// mark visited cells.
// Initially all cells
// are unvisited
bool[, ] visited = new bool[ROW, COL];
// Initialize count as 0 and
// traverse through the all
// cells of given matrix
int count = 0;
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (M[i, j] == 1 && !visited[i, j]) {
// If a cell with value 1 is not
// visited yet, then new island
// found, Visit all cells in this
// island and increment island count
DFS(M, i, j, visited);
++count;
}
return count;
}
// Driver Code
public static void Main()
{
int[, ] M = new int[, ] { { 1, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 1 },
{ 1, 0, 0, 1, 1 },
{ 0, 0, 0, 0, 0 },
{ 1, 0, 1, 0, 1 } };
Console.Write("Number of islands is: " + countIslands(M));
}
}
// This code is contributed
// by shiv_bhakt.
PHP
<?php
// Program to count islands
// in boolean 2D matrix
$ROW = 5;
$COL = 5;
// A function to check if a
// given cell (row, col) can
// be included in DFS
function isSafe(&$M, $row, $col,
&$visited)
{
global $ROW, $COL;
// row number is in range,
// column number is in
// range and value is 1
// and not yet visited
return ($row >= 0) && ($row < $ROW) &&
($col >= 0) && ($col < $COL) &&
($M[$row][$col] &&
!isset($visited[$row][$col]));
}
// A utility function to do DFS
// for a 2D boolean matrix. It
// only considers the 8 neighbours
// as adjacent vertices
function DFS(&$M, $row, $col,
&$visited)
{
// These arrays are used to
// get row and column numbers
// of 8 neighbours of a given cell
$rowNbr = array(-1, -1, -1, 0,
0, 1, 1, 1);
$colNbr = array(-1, 0, 1, -1,
1, -1, 0, 1);
// Mark this cell as visited
$visited[$row][$col] = true;
// Recur for all
// connected neighbours
for ($k = 0; $k < 8; ++$k)
if (isSafe($M, $row + $rowNbr[$k],
$col + $colNbr[$k], $visited))
DFS($M, $row + $rowNbr[$k],
$col + $colNbr[$k], $visited);
}
// The main function that returns
// count of islands in a given
// boolean 2D matrix
function countIslands(&$M)
{
global $ROW, $COL;
// Make a bool array to
// mark visited cells.
// Initially all cells
// are unvisited
$visited = array(array());
// Initialize count as 0 and
// traverse through the all
// cells of given matrix
$count = 0;
for ($i = 0; $i < $ROW; ++$i)
for ($j = 0; $j < $COL; ++$j)
if ($M[$i][$j] &&
!isset($visited[$i][$j])) // If a cell with value 1
{ // is not visited yet,
DFS($M, $i, $j, $visited); // then new island found
++$count; // Visit all cells in this
} // island and increment
// island count.
return $count;
}
// Driver Code
$M = array(array(1, 1, 0, 0, 0),
array(0, 1, 0, 0, 1),
array(1, 0, 0, 1, 1),
array(0, 0, 0, 0, 0),
array(1, 0, 1, 0, 1));
echo "Number of islands is: ",
countIslands($M);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to count islands in boolean 2D matrix
// No of rows and columns
let ROW = 5, COL = 5;
// A function to check if a given cell (row, col) can
// be included in DFS
function isSafe(M,row,col,visited)
{
// row number is in range, column number is in range
// and value is 1 and not yet visited
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
}
// A utility function to do DFS for a 2D boolean matrix.
// It only considers the 8 neighbors as adjacent vertices
function DFS(M, row, col, visited)
{
// These arrays are used to get row and column numbers
// of 8 neighbors of a given cell
let rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1];
let colNbr = [-1, 0, 1, -1, 1, -1, 0, 1];
// Mark this cell as visited
visited[row][col] = true;
// Recur for all connected neighbours
for (let k = 0; k < 8; ++k)
{
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
{
DFS(M, row + rowNbr[k], col + colNbr[k], visited);
}
}
}
// The main function that returns count of islands in a given
// boolean 2D matrix
function countIslands(M)
{
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
let visited = new Array(ROW);
for(let i = 0; i < ROW; i++)
{
visited[i] = new Array(COL);
}
for(let i = 0; i < ROW; i++)
{
for(let j = 0; j < COL; j++)
{
visited[i][j] = false;
}
}
// Initialize count as 0 and traverse through the all cells
// of given matrix
let count = 0;
for (let i = 0; i < ROW; ++i)
{
for (let j = 0; j < COL; ++j)
{
if (M[i][j] == 1 && !visited[i][j])
{
// value 1 is not
// visited yet, then new island found, Visit all
// cells in this island and increment island count
DFS(M, i, j, visited);
count++;
}
}
}
return count;
}
// Driver method
let M = [[ 1, 1, 0, 0, 0 ], [ 0, 1, 0, 0, 1],
[1, 0, 0, 1, 1] ,[0, 0, 0, 0, 0], [1, 0, 1, 0, 1]];
document.write("Number of islands is: " + countIslands(M));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Number of islands is: 5
Complejidad temporal: O(ROW x COL)
Espacio auxiliar: O(ROW x COL), debido a la array visitada
Solución alternativa sin crear array visitada:
C++
// C++Program to count islands in boolean 2D matrix
#include <bits/stdc++.h>
using namespace std;
// A utility function to do DFS for a 2D
// boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS(vector<vector<int>> &M, int i, int j, int ROW,
int COL)
{
//Base condition
//if i less than 0 or j less than 0 or i greater than ROW-1 or j greater than COL- or if M[i][j] != 1 then we will simply return
if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1) || M[i][j] != 1)
{
return;
}
if (M[i][j] == 1)
{
M[i][j] = 0;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
int countIslands(vector<vector<int>> &M)
{
int ROW = M.size();
int COL = M[0].size();
int count = 0;
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
if (M[i][j] == 1)
{
M[i][j] = 0;
count++;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
}
return count;
}
// Driver Code
int main()
{
vector<vector<int>> M = {{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}};
cout << "Number of islands is: " << countIslands(M);
return 0;
}
// This code is contributed by ajaymakvana.
Java
// Java Program to count islands in boolean 2D matrix
import java.util.*;
public class Main
{
// A utility function to do DFS for a 2D
// boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
static void DFS(int[][] M, int i, int j, int ROW, int COL)
{
// Base condition
// if i less than 0 or j less than 0 or i greater than ROW-1 or j greater than COL- or if M[i][j] != 1 then we will simply return
if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1) || M[i][j] != 1)
{
return;
}
if (M[i][j] == 1)
{
M[i][j] = 0;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
static int countIslands(int[][] M)
{
int ROW = M.length;
int COL = M[0].length;
int count = 0;
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
if (M[i][j] == 1)
{
M[i][j] = 0;
count++;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
}
return count;
}
// Driver code
public static void main(String[] args) {
int[][] M = {{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}};
System.out.print("Number of islands is: " + countIslands(M));
}
}
// This code is contributed by suresh07.
Python3
# Program to count islands in boolean 2D matrix
class Graph:
def __init__(self, row, col, graph):
self.ROW = row
self.COL = col
self.graph = graph
# A utility function to do DFS for a 2D
# boolean matrix. It only considers
# the 8 neighbours as adjacent vertices
def DFS(self, i, j):
if i < 0 or i >= len(self.graph) or j < 0 or j >= len(self.graph[0]) or self.graph[i][j] != 1:
return
# mark it as visited
self.graph[i][j] = -1
# Recur for 8 neighbours
self.DFS(i - 1, j - 1)
self.DFS(i - 1, j)
self.DFS(i - 1, j + 1)
self.DFS(i, j - 1)
self.DFS(i, j + 1)
self.DFS(i + 1, j - 1)
self.DFS(i + 1, j)
self.DFS(i + 1, j + 1)
# The main function that returns
# count of islands in a given boolean
# 2D matrix
def countIslands(self):
# Initialize count as 0 and traverse
# through the all cells of
# given matrix
count = 0
for i in range(self.ROW):
for j in range(self.COL):
# If a cell with value 1 is not visited yet,
# then new island found
if self.graph[i][j] == 1:
# Visit all cells in this island
# and increment island count
self.DFS(i, j)
count += 1
return count
graph = [
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]
]
row = len(graph)
col = len(graph[0])
g = Graph(row, col, graph)
print("Number of islands is:", g.countIslands())
# This code is contributed by Shivam Shrey
C#
// C# Program to count islands in boolean 2D matrix
using System;
using System.Collections.Generic;
class GFG {
// A utility function to do DFS for a 2D
// boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
static void DFS(int[,] M, int i, int j, int ROW, int COL)
{
// Base condition
// if i less than 0 or j less than 0 or i greater than ROW-1 or j greater than COL- or if M[i][j] != 1 then we will simply return
if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1) || M[i,j] != 1)
{
return;
}
if (M[i,j] == 1)
{
M[i,j] = 0;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
static int countIslands(int[,] M)
{
int ROW = M.GetLength(0);
int COL = M.GetLength(1);
int count = 0;
for (int i = 0; i < ROW; i++)
{
for (int j = 0; j < COL; j++)
{
if (M[i,j] == 1)
{
M[i,j] = 0;
count++;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
}
return count;
}
// Driver code
static void Main() {
int[,] M = {{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}};
Console.Write("Number of islands is: " + countIslands(M));
}
}
// This code is contributed by decode2207.
Javascript
<script>
// Javascript Program to count islands in boolean 2D matrix
// A utility function to do DFS for a 2D
// boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
function DFS(M, i, j, ROW, COL)
{
// Base condition
// if i less than 0 or j less than 0 or i greater than ROW-1 or j greater than COL- or if M[i][j] != 1 then we will simply return
if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1) || M[i][j] != 1)
{
return;
}
if (M[i][j] == 1)
{
M[i][j] = 0;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
function countIslands(M)
{
let ROW = M.length;
let COL = M[0].length;
let count = 0;
for (let i = 0; i < ROW; i++)
{
for (let j = 0; j < COL; j++)
{
if (M[i][j] == 1)
{
M[i][j] = 0;
count++;
DFS(M, i + 1, j, ROW, COL); //right side traversal
DFS(M, i - 1, j, ROW, COL); //left side traversal
DFS(M, i, j + 1, ROW, COL); //upward side traversal
DFS(M, i, j - 1, ROW, COL); //downward side traversal
DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
}
}
}
return count;
}
let M = [[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[1, 0, 1, 0, 1]];
document.write("Number of islands is: " + countIslands(M));
// This code is contributed by divyesh072019.
</script>
Producción
Number of islands is: 5
Complejidad de tiempo: O(ROW x COL)
Espacio auxiliar: O(1), ya que no estamos usando ningún espacio extra.
Encuentra el número de Islas | Conjunto 2 (usando conjunto disjunto)
Islas en un gráfico usando BFS
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA