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.
C++
// Program to count islands in boolean 2D matrix
#include <stdio.h>
#include <string.h>
#include <stdbool.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;
}
Number of islands is: 5
Complejidad Temporal: O(mxn), donde m y n son los números de filas y columnas de la array dada respectivamente.
Espacio auxiliar: O (mxn), para crear una array visitada de tamaño m, n .
Consulte el artículo completo sobre Encontrar el número de islas | ¡ Establezca 1 (usando DFS) para obtener más detalles!
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