Dada una array binaria mat[][] de dimensiones NxM tal que 1 denota la isla y 0 denota el agua. La tarea es encontrar el número de islas cerradas en la array dada.
Una isla cerrada se conoce como el grupo de 1 que está rodeado solo por 0 en los cuatro lados (excluyendo las diagonales). Si cualquier 1 está en los bordes de la array dada, entonces no se considera como la parte de la isla conectada ya que no está rodeado por todos los 0 .
Ejemplos:
Entrada: N = 5, M = 8,
mat[][] =
{{0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 1, 1, 1, 0, 0, 1},
{0, 1, 0, 1, 0, 0, 0, 1},
{0, 1, 1, 1, 1, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 1}}
Salida: 2
Explicación:
mat[][] =
{{0, 0, 0, 0, 0, 0, 0, 1},
{0, 1, 1, 1, 1, 0, 0, 1},
{0, 1 , 0, 1 , 0, 0, 0, 1},
{0, 1, 1, 1, 1, 0, 1 , 0},
{0, 0, 0, 0, 0, 0, 0, 1}}
Hay 2 islas cerradas.
Las islas en la oscuridad están cerradas porque están completamente rodeadas por
0s (agua).
Hay dos islas más en la última columna de la array, pero no están completamente rodeadas por ceros.
Por lo tanto, no son islas cerradas.Entrada: N = 3, M = 3, array[][] =
{{1, 0, 0},
{0, 1, 0},
{0, 0, 1}}
Salida: 1
Método 1: usar DFS Traversal : la idea es usar DFS Traversal para contar el número de islas rodeadas de agua. Pero tenemos que seguir el rastro de la isla en la esquina de la array dada, ya que no se contarán en la isla resultante. A continuación se muestran los pasos:
- Inicialice una array visitada en 2D (digamos vis[][] ) para mantener el seguimiento de la celda atravesada en la array dada.
- Realice DFS Traversal en todas las esquinas de la array dada y, si algún elemento tiene el valor 1, marque todas las celdas con el valor 1 como visitadas porque no se pueden contar en el recuento resultante.
- Realice DFS Traversal en todas las celdas no visitadas restantes y, si el valor encontrado es 1, marque esta celda como visitada, cuente esta isla en el conteo resultante y llame recursivamente a DFS para las 4 direcciones, es decir, izquierda, derecha, arriba y abajo para hacer todos los 1 conectados a la celda actual como visitados.
- Repita el paso anterior hasta que no se visiten todas las celdas con valor 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // DFS Traversal to find the count of // island surrounded by water void dfs(vector<vector<int> >& matrix, vector<vector<bool> >& visited, int x, int y, int n, int m) { // If the land is already visited // or there is no land or the // coordinates gone out of matrix // break function as there // will be no islands if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y] == true || matrix[x][y] == 0) return; // Mark land as visited visited[x][y] = true; // Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m); dfs(matrix, visited, x, y + 1, n, m); dfs(matrix, visited, x - 1, y, n, m); dfs(matrix, visited, x, y - 1, n, m); } // Function that counts the closed island int countClosedIsland(vector<vector<int> >& matrix, int n, int m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. vector<vector<bool> > visited(n, vector<bool>(m, false)); // Mark visited all lands // that are reachable from edge for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // Traverse corners if ((i * j == 0 || i == n - 1 || j == m - 1) and matrix[i][j] == 1 and visited[i][j] == false) dfs(matrix, visited, i, j, n, m); } } // To stores number of closed islands int result = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // If the land not visited // then there will be atleast // one closed island if (visited[i][j] == false and matrix[i][j] == 1) { result++; // Mark all lands associated // with island visited. dfs(matrix, visited, i, j, n, m); } } } // Return the final count return result; } // Driver Code int main() { // Given size of Matrix int N = 5, M = 8; // Given Matrix vector<vector<int> > matrix = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function Call cout << countClosedIsland(matrix, N, M); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // DFS Traversal to find the count of // island surrounded by water static void dfs(int[][] matrix, boolean[][] visited, int x, int y, int n, int m) { // If the land is already visited // or there is no land or the // coordinates gone out of matrix // break function as there // will be no islands if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y] == true || matrix[x][y] == 0) return; // Mark land as visited visited[x][y] = true; // Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m); dfs(matrix, visited, x, y + 1, n, m); dfs(matrix, visited, x - 1, y, n, m); dfs(matrix, visited, x, y - 1, n, m); } // Function that counts the closed island static int countClosedIsland(int[][] matrix, int n, int m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. boolean[][] visited = new boolean[n][m]; // Mark visited all lands // that are reachable from edge for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // Traverse corners if ((i * j == 0 || i == n - 1 || j == m - 1) && matrix[i][j] == 1 && visited[i][j] == false) dfs(matrix, visited, i, j, n, m); } } // To stores number of closed islands int result = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // If the land not visited // then there will be atleast // one closed island if (visited[i][j] == false && matrix[i][j] == 1) { result++; // Mark all lands associated // with island visited. dfs(matrix, visited, i, j, n, m); } } } // Return the final count return result; } // Driver Code public static void main(String[] args) { // Given size of Matrix int N = 5, M = 8; // Given Matrix int[][] matrix = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function Call System.out.print(countClosedIsland(matrix, N, M)); } } // This code is contributed by Rohit_ranjan
Python3
# Python3 program for the above approach # DFS Traversal to find the count of # island surrounded by water def dfs(matrix, visited, x, y, n, m): # If the land is already visited # or there is no land or the # coordinates gone out of matrix # break function as there # will be no islands if (x < 0 or y < 0 or x >= n or y >= m or visited[x][y] == True or matrix[x][y] == 0): return # Mark land as visited visited[x][y] = True # Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m); dfs(matrix, visited, x, y + 1, n, m); dfs(matrix, visited, x - 1, y, n, m); dfs(matrix, visited, x, y - 1, n, m); # Function that counts the closed island def countClosedIsland(matrix, n, m): # Create boolean 2D visited matrix # to keep track of visited cell # Initially all elements are # unvisited. visited = [[False for i in range(m)] for j in range(n)] # Mark visited all lands # that are reachable from edge for i in range(n): for j in range(m): # Traverse corners if ((i * j == 0 or i == n - 1 or j == m - 1) and matrix[i][j] == 1 and visited[i][j] == False): dfs(matrix, visited, i, j, n, m) # To stores number of closed islands result = 0 for i in range(n): for j in range(m): # If the land not visited # then there will be atleast # one closed island if (visited[i][j] == False and matrix[i][j] == 1): result += 1 # Mark all lands associated # with island visited. dfs(matrix, visited, i, j, n, m) # Return the final count return result # Driver Code # Given size of Matrix N = 5 M = 8 # Given Matrix matrix = [ [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 0, 1 ], [ 0, 1, 0, 1, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1 ] ] # Function Call print(countClosedIsland(matrix, N, M)) # This code is contributed by rag2127
C#
// C# program for the above approach using System; class GFG { // DFS Traversal to find the count of // island surrounded by water static void dfs(int[, ] matrix, bool[, ] visited, int x, int y, int n, int m) { // If the land is already visited // or there is no land or the // coordinates gone out of matrix // break function as there // will be no islands if (x < 0 || y < 0 || x >= n || y >= m || visited[x, y] == true || matrix[x, y] == 0) return; // Mark land as visited visited[x, y] = true; // Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m); dfs(matrix, visited, x, y + 1, n, m); dfs(matrix, visited, x - 1, y, n, m); dfs(matrix, visited, x, y - 1, n, m); } // Function that counts the closed island static int countClosedIsland(int[, ] matrix, int n, int m) { // Create bool 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. bool[, ] visited = new bool[n, m]; // Mark visited all lands // that are reachable from edge for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // Traverse corners if ((i * j == 0 || i == n - 1 || j == m - 1) && matrix[i, j] == 1 && visited[i, j] == false) dfs(matrix, visited, i, j, n, m); } } // To stores number of closed islands int result = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // If the land not visited // then there will be atleast // one closed island if (visited[i, j] == false && matrix[i, j] == 1) { result++; // Mark all lands associated // with island visited. dfs(matrix, visited, i, j, n, m); } } } // Return the readonly count return result; } // Driver Code public static void Main(String[] args) { // Given size of Matrix int N = 5, M = 8; // Given Matrix int[, ] matrix = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function call Console.Write(countClosedIsland(matrix, N, M)); } } // This code is contributed by amal kumar choubey
Javascript
<script> // JavaScript program for the above approach // DFS Traversal to find the count of // island surrounded by water function dfs(matrix, visited, x, y, n, m) { // If the land is already visited // or there is no land or the // coordinates gone out of matrix // break function as there // will be no islands if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y] == true || matrix[x][y] == 0) return; // Mark land as visited visited[x][y] = true; // Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m); dfs(matrix, visited, x, y + 1, n, m); dfs(matrix, visited, x - 1, y, n, m); dfs(matrix, visited, x, y - 1, n, m); } // Function that counts the closed island function countClosedIsland(matrix, n, m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. let visited = new Array(n); for (let i = 0; i < n; ++i) { visited[i] = new Array(m); for (let j = 0; j < m; ++j) { visited[i][j] = false; } } // Mark visited all lands // that are reachable from edge for (let i = 0; i < n; ++i) { for (let j = 0; j < m; ++j) { // Traverse corners if ((i * j == 0 || i == n - 1 || j == m - 1) && matrix[i][j] == 1 && visited[i][j] == false) dfs(matrix, visited, i, j, n, m); } } // To stores number of closed islands let result = 0; for (let i = 0; i < n; ++i) { for (let j = 0; j < m; ++j) { // If the land not visited // then there will be atleast // one closed island if (visited[i][j] == false && matrix[i][j] == 1) { result++; // Mark all lands associated // with island visited. dfs(matrix, visited, i, j, n, m); } } } // Return the final count return result; } // Given size of Matrix let N = 5, M = 8; // Given Matrix let matrix = [ [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 0, 1 ], [ 0, 1, 0, 1, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1 ] ]; // Function Call document.write(countClosedIsland(matrix, N, M)); </script>
2
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Método: recorrido DFS único
Mejora sobre el Método 1: en el Método 1 anterior, vemos que estamos llamando a DFS transversal dos veces (una vez sobre las celdas de las esquinas con ‘1’ y luego sobre las celdas que no están en las esquinas con ‘1’ y no se visitan) . Podemos resolver esto usando solo 1 recorrido DFS. la idea es llamar a DFS para las celdas con el valor ‘1’ que no están en las esquinas y, al hacerlo, si encontramos una celda con el valor ‘1’ en la esquina, eso significa que no debe contarse como una isla . El código se muestra a continuación:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // DFS Traversal to find the count of // island surrounded by water void dfs(vector<vector<int> >& matrix, vector<vector<bool> >& visited, int x, int y, int n, int m, bool &hasCornerCell) { // If the land is already visited // or there is no land or the // coordinates gone out of matrix // break function as there // will be no islands if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y] == true || matrix[x][y] == 0) return; // Check for the corner cell if(x == 0 || y == 0 || x == n-1 || y == m-1) { if(matrix[x][y] == 1) hasCornerCell = true; } // Mark land as visited visited[x][y] = true; // Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m, hasCornerCell); dfs(matrix, visited, x, y + 1, n, m, hasCornerCell); dfs(matrix, visited, x - 1, y, n, m, hasCornerCell); dfs(matrix, visited, x, y - 1, n, m, hasCornerCell); } // Function that counts the closed island int countClosedIsland(vector<vector<int> >& matrix, int n, int m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. vector<vector<bool>> visited(n,vector<bool>(m, false)); // Store the count of islands int result = 0; // Call DFS on the cells which // are not on corners with value '1' for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if ((i != 0 && j != 0 && i != n - 1 && j != m - 1) and matrix[i][j] == 1 and visited[i][j] == false) { // Determine if the island is closed bool hasCornerCell = false; /* hasCornerCell will be updated to true while DFS traversal if there is a cell with value '1' on the corner */ dfs(matrix, visited, i, j, n, m, hasCornerCell); /* If the island is closed*/ if(!hasCornerCell) result = result + 1; } } } // Return the final count return result; } // Driver Code int main() { // Given size of Matrix int N = 5, M = 8; // Given Matrix vector<vector<int> > matrix = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function Call cout << countClosedIsland(matrix, N, M); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // DFS Traversal to find the count of // island surrounded by water static void dfs(int[][] matrix, boolean[][] visited, int x, int y, int n, int m, boolean hasCornerCell) { // If the land is already visited // or there is no land or the // coordinates gone out of matrix // break function as there // will be no islands if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y] == true || matrix[x][y] == 0) return; if (x == 0 || y == 0 || x == n - 1 || y == m - 1) { if (matrix[x][y] == 1) hasCornerCell = true; } // Mark land as visited visited[x][y] = true; // Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m, hasCornerCell); dfs(matrix, visited, x, y + 1, n, m, hasCornerCell); dfs(matrix, visited, x - 1, y, n, m, hasCornerCell); dfs(matrix, visited, x, y - 1, n, m, hasCornerCell); } // Function that counts the closed island static int countClosedIsland(int[][] matrix, int n, int m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. boolean[][] visited = new boolean[n][m]; int result = 0; // Mark visited all lands // that are reachable from edge for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { if ((i != 0 && j != 0 && i != n - 1 && j != m - 1) && matrix[i][j] == 1 && visited[i][j] == false) { // Determine if the island is closed boolean hasCornerCell = false; // hasCornerCell will be updated to // true while DFS traversal if there // is a cell with value '1' on the corner dfs(matrix, visited, i, j, n, m, hasCornerCell); // If the island is closed if (!hasCornerCell) result = result + 1; } } } // Return the final count return result; } // Driver Code public static void main(String[] args) { // Given size of Matrix int N = 5, M = 8; // Given Matrix int[][] matrix = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function Call System.out.print(countClosedIsland(matrix, N, M)); } } // This code is contributed by grand_master
Python3
# Python3 program for the above approach # DFS Traversal to find the count of # island surrounded by water def dfs(matrix, visited, x, y, n, m, hasCornerCell): # If the land is already visited # or there is no land or the # coordinates gone out of matrix # break function as there # will be no islands if (x < 0 or y < 0 or x >= n or y >= m or visited[x][y] == True or matrix[x][y] == 0): return if (x == 0 or y == 0 or x == n - 1 or y == m - 1): if (matrix[x][y] == 1): hasCornerCell = True # Mark land as visited visited[x][y] = True # Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m, hasCornerCell) dfs(matrix, visited, x, y + 1, n, m, hasCornerCell) dfs(matrix, visited, x - 1, y, n, m, hasCornerCell) dfs(matrix, visited, x, y - 1, n, m, hasCornerCell) # Function that counts the closed island def countClosedIsland(matrix, n, m): # Create boolean 2D visited matrix # to keep track of visited cell # Initially all elements are # unvisited. visited = [[False for i in range(m)] for j in range(n)] result = 0 # Mark visited all lands # that are reachable from edge for i in range(n): for j in range(m): if ((i != 0 and j != 0 and i != n - 1 and j != m - 1) and matrix[i][j] == 1 and visited[i][j] == False): # Determine if the island is closed hasCornerCell = False # hasCornerCell will be updated to # true while DFS traversal if there # is a cell with value '1' on the corner dfs(matrix, visited, i, j, n, m, hasCornerCell) # If the island is closed if (not hasCornerCell): result = result + 1 # Return the final count return result # Driver Code # Given size of Matrix N, M = 5, 8 # Given Matrix matrix = [ [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 0, 1 ], [ 0, 1, 0, 1, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1 ] ] # Function Call print(countClosedIsland(matrix, N, M)) # This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach using System; class GFG { // DFS Traversal to find the count of // island surrounded by water static void dfs(int[,] matrix, bool[,] visited, int x, int y, int n, int m, bool hasCornerCell) { // If the land is already visited // or there is no land or the // coordinates gone out of matrix // break function as there // will be no islands if (x < 0 || y < 0 || x >= n || y >= m || visited[x, y] == true || matrix[x, y] == 0) return; if (x == 0 || y == 0 || x == n - 1 || y == m - 1) { if (matrix[x, y] == 1) hasCornerCell = true; } // Mark land as visited visited[x, y] = true; // Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m, hasCornerCell); dfs(matrix, visited, x, y + 1, n, m, hasCornerCell); dfs(matrix, visited, x - 1, y, n, m, hasCornerCell); dfs(matrix, visited, x, y - 1, n, m, hasCornerCell); } // Function that counts the closed island static int countClosedIsland(int[,] matrix, int n, int m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. bool[,] visited = new bool[n, m]; int result = 0; // Mark visited all lands // that are reachable from edge for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { if ((i != 0 && j != 0 && i != n - 1 && j != m - 1) && matrix[i, j] == 1 && visited[i, j] == false) { // Determine if the island is closed bool hasCornerCell = false; // hasCornerCell will be updated to // true while DFS traversal if there // is a cell with value '1' on the corner dfs(matrix, visited, i, j, n, m, hasCornerCell); // If the island is closed if (!hasCornerCell) result = result + 1; } } } // Return the final count return result; } // Driver code static void Main() { // Given size of Matrix int N = 5, M = 8; // Given Matrix int[,] matrix = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function Call Console.WriteLine(countClosedIsland(matrix, N, M)); } } // This code is contributed by divyesh072019
Javascript
<script> // JavaScript program for the above approach // DFS Traversal to find the count of // island surrounded by water function dfs(matrix, visited, x, y, n, m, hasCornerCell) { // If the land is already visited // or there is no land or the // coordinates gone out of matrix // break function as there // will be no islands if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y] == true || matrix[x][y] == 0) return; if (x == 0 || y == 0 || x == n - 1 || y == m - 1) { if (matrix[x][y] == 1) hasCornerCell = true; } // Mark land as visited visited[x][y] = true; // Traverse to all adjacent elements dfs(matrix, visited, x + 1, y, n, m, hasCornerCell); dfs(matrix, visited, x, y + 1, n, m, hasCornerCell); dfs(matrix, visited, x - 1, y, n, m, hasCornerCell); dfs(matrix, visited, x, y - 1, n, m, hasCornerCell); } // Function that counts the closed island function countClosedIsland(matrix, n, m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. let visited = new Array(n); for(let i = 0; i < n; ++i) { visited[i] = new Array(m); for(let j = 0; j < m; ++j) { visited[i][j] = false; } } let result = 0; // Mark visited all lands // that are reachable from edge for(let i = 0; i < n; ++i) { for(let j = 0; j < m; ++j) { if ((i != 0 && j != 0 && i != n - 1 && j != m - 1) && matrix[i][j] == 1 && visited[i][j] == false) { // Determine if the island is closed let hasCornerCell = false; // hasCornerCell will be updated to // true while DFS traversal if there // is a cell with value '1' on the corner dfs(matrix, visited, i, j, n, m, hasCornerCell); // If the island is closed if (!hasCornerCell) result = result + 1; } } } // Return the final count return result; } // Given size of Matrix let N = 5, M = 8; // Given Matrix let matrix = [ [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 0, 1 ], [ 0, 1, 0, 1, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1 ] ]; // Function Call document.write(countClosedIsland(matrix, N, M)); </script>
2
Método 2: usar BFS Traversal : la idea es visitar cada celda con valor 1 en la esquina usando BFS y luego atravesar la array dada y si se encuentra alguna celda no visitada con valor 1, entonces incremente el conteo de la isla y haga todos los 1 conectado a él como visitado. A continuación se muestran los pasos:
- Inicialice una array visitada en 2D (digamos vis[][] ) para mantener el seguimiento de la celda atravesada en la array dada.
- Realice BFS Traversal en todas las esquinas de la array dada y, si algún elemento tiene el valor 1, marque todas las celdas con el valor 1 como visitadas porque no se pueden contar en el recuento resultante.
- Realice BFS Traversal en todas las celdas no visitadas restantes y, si el valor encontrado es 1, marque esta celda como visitada, cuente esta isla en el conteo resultante y marque cada celda en las 4 direcciones, es decir, izquierda, derecha, arriba y abajo para hacer todos los 1 conectados a la celda actual como visitados.
- Repita el paso anterior hasta que no se visiten todas las celdas con valor 1.
- Imprima el conteo de islas después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int dx[] = { -1, 0, 1, 0 }; int dy[] = { 0, 1, 0, -1 }; // DFS Traversal to find the count of // island surrounded by water void bfs(vector<vector<int> >& matrix, vector<vector<bool> >& visited, int x, int y, int n, int m) { // To store the popped cell pair<int, int> temp; // To store the cell of BFS queue<pair<int, int> > Q; // Push the current cell Q.push({ x, y }); // Until Q is not empty while (!Q.empty()) { temp = Q.front(); Q.pop(); // Mark current cell // as visited visited[temp.first] [temp.second] = true; // Iterate in all four directions for (int i = 0; i < 4; i++) { int x = temp.first + dx[i]; int y = temp.second + dy[i]; // Cell out of the matrix if (x < 0 || y < 0 || x >= n || y >= m || visited[x][y] == true || matrix[x][y] == 0) { continue; } // Check is adjacent cell is // 1 and not visited if (visited[x][y] == false && matrix[x][y] == 1) { Q.push({ x, y }); } } } } // Function that counts the closed island int countClosedIsland(vector<vector<int> >& matrix, int n, int m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. vector<vector<bool> > visited( n, vector<bool>(m, false)); // Mark visited all lands // that are reachable from edge for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // Traverse corners if ((i * j == 0 || i == n - 1 || j == m - 1) and matrix[i][j] == 1 and visited[i][j] == false) { bfs(matrix, visited, i, j, n, m); } } } // To stores number of closed islands int result = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { // If the land not visited // then there will be atleast // one closed island if (visited[i][j] == false and matrix[i][j] == 1) { result++; // Mark all lands associated // with island visited bfs(matrix, visited, i, j, n, m); } } } // Return the final count return result; } // Driver Code int main() { // Given size of Matrix int N = 5, M = 8; // Given Matrix vector<vector<int> > matrix = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function Call cout << countClosedIsland(matrix, N, M); return 0; }
Java
// Java program for the above approach import java.util.LinkedList; import java.util.Queue; class GFG{ static int dx[] = { -1, 0, 1, 0 }; static int dy[] = { 0, 1, 0, -1 }; // To store the row and columne index // of the popped cell static class Cell { int first, second; Cell(int x, int y) { this.first = x; this.second = y; } } // BFS Traversal to find the count of // island surrounded by water static void bfs(int[][] matrix, boolean[][] visited, int x, int y, int n, int m) { // To store the popped cell Cell temp; // To store the cell of BFS Queue<Cell> Q = new LinkedList<Cell>(); // Push the current cell Q.add(new Cell(x, y)); // Until Q is not empty while (!Q.isEmpty()) { temp = Q.peek(); Q.poll(); // Mark current cell // as visited visited[temp.first][temp.second] = true; // Iterate in all four directions for(int i = 0; i < 4; i++) { int xIndex = temp.first + dx[i]; int yIndex = temp.second + dy[i]; // Cell out of the matrix if (xIndex < 0 || yIndex < 0 || xIndex >= n || yIndex >= m || visited[xIndex][yIndex] == true || matrix[xIndex][yIndex] == 0) { continue; } // Check is adjacent cell is // 1 and not visited if (visited[xIndex][yIndex] == false && matrix[xIndex][yIndex] == 1) { Q.add(new Cell(xIndex, yIndex)); } } } } // Function that counts the closed island static int countClosedIsland(int[][] matrix, int n, int m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. boolean[][] visited = new boolean[n][m]; // Mark visited all lands // that are reachable from edge for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { // Traverse corners if ((i * j == 0 || i == n - 1 || j == m - 1) && matrix[i][j] == 1 && visited[i][j] == false) { bfs(matrix, visited, i, j, n, m); } } } // To stores number of closed islands int result = 0; for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { // If the land not visited // then there will be atleast // one closed island if (visited[i][j] == false && matrix[i][j] == 1) { result++; // Mark all lands associated // with island visited bfs(matrix, visited, i, j, n, m); } } } // Return the final count return result; } // Driver Code public static void main(String[] args) { // Given size of Matrix int N = 5, M = 8; // Given Matrix int[][] matrix = { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function Call System.out.println(countClosedIsland(matrix, N, M)); } } // This code is contributed by jainlovely450
Python3
# Python program for the above approach dx = [-1, 0, 1, 0 ] dy = [0, 1, 0, -1] global matrix # DFS Traversal to find the count of # island surrounded by water def bfs(x, y, n, m): # To store the popped cell temp = [] # To store the cell of BFS Q = [] # Push the current cell Q.append([x, y]) # Until Q is not empty while(len(Q) > 0): temp = Q.pop() # Mark current cell # as visited visited[temp[0]][temp[1]] = True # Iterate in all four directions for i in range(4): x = temp[0] + dx[i] y = temp[1] + dy[i] # Cell out of the matrix if(x < 0 or y < 0 or x >= n or y >= n or visited[x][y] == True or matrix[x][y] == 0): continue # Check is adjacent cell is # 1 and not visited if(visited[x][y] == False and matrix[x][y] == 1): Q.append([x, y]) # Function that counts the closed island def countClosedIsland(n, m): # Create boolean 2D visited matrix # to keep track of visited cell # Initially all elements are # unvisited. global visited visited = [[False for i in range(m)] for j in range(n)] # Mark visited all lands # that are reachable from edge for i in range(n): for j in range(m): # Traverse corners if((i * j == 0 or i == n - 1 or j == m - 1) and matrix[i][j] == 1 and visited[i][j] == False): bfs(i, j, n, m); # To stores number of closed islands result = 0 for i in range(n): for j in range(m): # If the land not visited # then there will be atleast # one closed island if(visited[i][j] == False and matrix[i][j] == 1): result += 1 # Mark all lands associated # with island visited bfs(i, j, n, m); # Return the final count return result # Driver Code # Given size of Matrix N = 5 M = 8 # Given Matrix matrix = [[ 0, 0, 0, 0, 0, 0, 0, 1], [0, 1, 1, 1, 1, 0, 0, 1], [0, 1, 0, 1, 0, 0, 0, 1 ], [0, 1, 1, 1, 1, 0, 1, 0 ], [0, 0, 0, 0, 0, 0, 0, 1]] # Function Call print(countClosedIsland(N, M)) # This code is contributed by avanitrachhadiya2155
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { static int[,] matrix; static bool[,] visited; static int[] dx = {-1, 0, 1, 0 }; static int[] dy = {0, 1, 0, -1}; // DFS Traversal to find the count of // island surrounded by water static void bfs(int x, int y, int n, int m) { // To store the popped cell Tuple<int,int> temp; // To store the cell of BFS List<Tuple<int,int>> Q = new List<Tuple<int,int>>(); // Push the current cell Q.Add(new Tuple<int, int>(x, y)); // Until Q is not empty while(Q.Count <= 0) { temp = Q[0]; Q.RemoveAt(0); // Mark current cell // as visited visited[temp.Item1,temp.Item2] = true; // Iterate in all four directions for(int i = 0; i < 4; i++) { int xIndex = temp.Item1 + dx[i]; int yIndex = temp.Item2 + dy[i]; // Cell out of the matrix if (xIndex < 0 || yIndex < 0 || xIndex >= n || yIndex >= m || visited[xIndex,yIndex] == true || matrix[xIndex,yIndex] == 0) { continue; } // Check is adjacent cell is // 1 and not visited if (visited[xIndex,yIndex] == false && matrix[xIndex,yIndex] == 1) { Q.Add(new Tuple<int, int>(x, y)); } } } } // Function that counts the closed island static int countClosedIsland(int n, int m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. visited = new bool[n, m]; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { visited[i,j] = false; } } // Mark visited all lands // that are reachable from edge for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // Traverse corners if((i * j == 0 || i == n - 1 || j == m - 1) && matrix[i,j] == 1 && visited[i,j] == false) { bfs(i, j, n, m); } } } // To stores number of closed islands int result = 2; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // If the land not visited // then there will be atleast // one closed island if(visited[i,j] == false && matrix[i,j] == 1) { result = 2; // Mark all lands associated // with island visited bfs(i, j, n, m); } } } // Return the final count return result; } static void Main() { // Given size of Matrix int N = 5, M = 8; // Given Matrix matrix = new int[5,8] { { 0, 0, 0, 0, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 0, 1 }, { 0, 1, 0, 1, 0, 0, 0, 1 }, { 0, 1, 1, 1, 1, 0, 1, 0 }, { 0, 0, 0, 0, 0, 0, 0, 1 } }; // Function Call Console.Write(countClosedIsland(N, M)); } } // This code is contributed by rameshtravel07.
Javascript
<script> // Javascript program for the above approach let matrix; let visited; let dx = [-1, 0, 1, 0 ]; let dy = [0, 1, 0, -1]; // DFS Traversal to find the count of // island surrounded by water function bfs(x, y, n, m) { // To store the popped cell let temp; // To store the cell of BFS let Q = []; // Push the current cell Q.push([x, y]); // Until Q is not empty while(Q.length > 0) { temp = Q[0]; Q.pop(); // Mark current cell // as visited visited[temp[0]][temp[1]] = true; // Iterate in all four directions for(let i = 0; i < 4; i++) { let x = temp[0] + dx[i]; let y = temp[1] + dy[i]; // Cell out of the matrix if(x < 0 || y < 0 || x >= n || y >= n || visited[x][y] == true || matrix[x][y] == 0) { continue; } // Check is adjacent cell is // 1 and not visited if(visited[x][y] == false && matrix[x][y] == 1) { Q.push([x, y]); } } } } // Function that counts the closed island function countClosedIsland(n, m) { // Create boolean 2D visited matrix // to keep track of visited cell // Initially all elements are // unvisited. visited = new Array(n); for(let i = 0; i < n; i++) { visited[i] = new Array(m); for(let j = 0; j < m; j++) { visited[i][j] = false; } } // Mark visited all lands // that are reachable from edge for(let i = 0; i < n; i++) { for(let j = 0; j < m; j++) { // Traverse corners if((i * j == 0 || i == n - 1 || j == m - 1) && matrix[i][j] == 1 && visited[i][j] == false) { bfs(i, j, n, m); } } } // To stores number of closed islands let result = 2; for(let i = 0; i < n; i++) { for(let j = 0; j < m; j++) { // If the land not visited // then there will be atleast // one closed island if(visited[i][j] == false && matrix[i][j] == 1) { result += 1; // Mark all lands associated // with island visited bfs(i, j, n, m); } } } // Return the final count return result; } // Given size of Matrix let N = 5, M = 8; // Given Matrix matrix = [ [ 0, 0, 0, 0, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 0, 1 ], [ 0, 1, 0, 1, 0, 0, 0, 1 ], [ 0, 1, 1, 1, 1, 0, 1, 0 ], [ 0, 0, 0, 0, 0, 0, 0, 1 ] ]; // Function Call document.write(countClosedIsland(matrix, N, M)); // This code is contributed by decode2207. </script>
2
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Método 3 – usando Disjoint-Set(Union-Find) :
- Recorre la array dada y cambia todos los 1 y los conectados en las esquinas de la array a 0 .
- Ahora atraviese la array nuevamente, y para todo el conjunto de 1 conectados, cree un borde que se conecte a todos los 1.
- Encuentre los componentes conectados para todos los bordes almacenados utilizando Disjoint-Set Approach.
- Imprima el recuento de componentes después de los pasos anteriores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that implements the Find int Find(vector<int>& hashSet, int val) { // Get the val int parent = val; // Until parent is not found while (parent != hashSet[parent]) { parent = hashSet[parent]; } // Return the parent return parent; } // Function that implements the Union void Union(vector<int>& hashSet, int first, int second) { // Find the first father int first_father = Find(hashSet, first); // Find the second father int second_father = Find(hashSet, second); // If both are unequals then update // first father as ssecond_father if (first_father != second_father) hashSet[first_father] = second_father; } // Recursive Function that change all // the corners connected 1s to 0s void change(vector<vector<char> >& matrix, int x, int y, int n, int m) { // If already zero then return if (x < 0 || y < 0 || x > m - 1 || y > n - 1 || matrix[x][y] == '0') return; // Change the current cell to '0' matrix[x][y] = '0'; // Recursive Call for all the // four corners change(matrix, x + 1, y, n, m); change(matrix, x, y + 1, n, m); change(matrix, x - 1, y, n, m); change(matrix, x, y - 1, n, m); } // Function that changes all the // connected 1s to 0s at the corners void changeCorner(vector<vector<char> >& matrix) { // Dimensions of matrix int m = matrix.size(); int n = matrix[0].size(); // Traverse the matrix for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // If corner cell if (i * j == 0 || i == m - 1 || j == n - 1) { // If value is 1s, then // recursively change to 0 if (matrix[i][j] == '1') { change(matrix, i, j, n, m); } } } } } // Function that counts the number // of island in the given matrix int numIslands(vector<vector<char> >& matrix) { if (matrix.size() == 0) return 0; // Dimensions of the matrix int m = matrix.size(); int n = matrix[0].size(); // Make all the corners connecting // 1s to zero changeCorner(matrix); // First convert to 1 dimension // position and convert all the // connections to edges vector<pair<int, int> > edges; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // If the cell value is 1 if (matrix[i][j] == '1') { int id = i * n + j; // Move right if (j + 1 < n) { // If right cell is // 1 then make it as // an edge if (matrix[i][j + 1] == '1') { int right = i * n + j + 1; // Push in edge vector edges.push_back(make_pair(id, right)); } } // Move down if (i + 1 < m) { // If right cell is // 1 then make it as // an edge if (matrix[i + 1][j] == '1') { int down = (i + 1) * n + j; // Push in edge vector edges.push_back(make_pair(id, down)); } } } } } // Construct the Union Find structure vector<int> hashSet(m * n, 0); for (int i = 0; i < m * n; i++) { hashSet[i] = i; } // Next apply Union Find for all // the edges stored for (auto edge : edges) { Union(hashSet, edge.first, edge.second); } // To count the number of connected // islands int numComponents = 0; // Traverse to find the islands for (int i = 0; i < m * n; i++) { if (matrix[i / n][i % n] == '1' && hashSet[i] == i) numComponents++; } // Return the count of the island return numComponents; } // Driver Code int main() { // Given size of Matrix int N = 5, M = 8; // Given Matrix vector<vector<char> > matrix = { { '0', '0', '0', '0', '0', '0', '0', '1' }, { '0', '1', '1', '1', '1', '0', '0', '1' }, { '0', '1', '0', '1', '0', '0', '0', '1' }, { '0', '1', '1', '1', '1', '0', '1', '0' }, { '0', '0', '0', '0', '0', '0', '0', '1' } }; // Function Call cout << numIslands(matrix); return 0; }
Java
// Java program for the above approach import java.util.ArrayList; class GFG{ static class Edge { int first, second; Edge(int x, int y) { this.first = x; this.second = y; } } // Function that implements the Find static int Find(int[] hashSet, int val) { // Get the val int parent = val; // Until parent is not found while (parent != hashSet[parent]) { parent = hashSet[parent]; } // Return the parent return parent; } // Function that implements the Union static void Union(int[] hashSet, int first, int second) { // Find the first father int first_father = Find(hashSet, first); // Find the second father int second_father = Find(hashSet, second); // If both are unequals then update // first father as ssecond_father if (first_father != second_father) hashSet[first_father] = second_father; } // Recursive Function that change all // the corners connected 1s to 0s static void change(char[][] matrix, int x, int y, int n, int m) { // If already zero then return if (x < 0 || y < 0 || x > m - 1 || y > n - 1 || matrix[x][y] == '0') return; // Change the current cell to '0' matrix[x][y] = '0'; // Recursive Call for all the // four corners change(matrix, x + 1, y, n, m); change(matrix, x, y + 1, n, m); change(matrix, x - 1, y, n, m); change(matrix, x, y - 1, n, m); } // Function that changes all the // connected 1s to 0s at the corners static void changeCorner(char[][] matrix) { // Dimensions of matrix int m = matrix.length; int n = matrix[0].length; // Traverse the matrix for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { // If corner cell if (i * j == 0 || i == m - 1 || j == n - 1) { // If value is 1s, then // recursively change to 0 if (matrix[i][j] == '1') { change(matrix, i, j, n, m); } } } } } // Function that counts the number // of island in the given matrix static int numIslands(char[][] matrix) { if (matrix.length == 0) return 0; // Dimensions of the matrix int m = matrix.length; int n = matrix[0].length; // Make all the corners connecting // 1s to zero changeCorner(matrix); // First convert to 1 dimension // position and convert all the // connections to edges ArrayList<Edge> edges = new ArrayList<Edge>(); for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { // If the cell value is 1 if (matrix[i][j] == '1') { int id = i * n + j; // Move right if (j + 1 < n) { // If right cell is // 1 then make it as // an edge if (matrix[i][j + 1] == '1') { int right = i * n + j + 1; // Push in edge vector edges.add(new Edge(id, right)); } } // Move down if (i + 1 < m) { // If right cell is // 1 then make it as // an edge if (matrix[i + 1][j] == '1') { int down = (i + 1) * n + j; // Push in edge vector edges.add(new Edge(id, down)); } } } } } // Construct the Union Find structure int[] hashSet = new int[m * n]; for(int i = 0; i < m * n; i++) { hashSet[i] = i; } // Next apply Union Find for all // the edges stored for(Edge edge : edges) { Union(hashSet, edge.first, edge.second); } // To count the number of connected // islands int numComponents = 0; // Traverse to find the islands for(int i = 0; i < m * n; i++) { if (matrix[i / n][i % n] == '1' && hashSet[i] == i) numComponents++; } // Return the count of the island return numComponents; } // Driver Code public static void main(String[] args) { // Given size of Matrix int N = 5, M = 8; // Given Matrix char[][] matrix = { { '0', '0', '0', '0', '0', '0', '0', '1' }, { '0', '1', '1', '1', '1', '0', '0', '1' }, { '0', '1', '0', '1', '0', '0', '0', '1' }, { '0', '1', '1', '1', '1', '0', '1', '0' }, { '0', '0', '0', '0', '0', '0', '0', '1' } }; // Function Call System.out.println(numIslands(matrix)); } } // This code is contributed by jainlovely450
Python3
# python 3 program for the above approach # Function that implements the Find def Find(hashSet, val): # Get the val parent = val # Until parent is not found while (parent != hashSet[parent]): parent = hashSet[parent] # Return the parent return parent # Function that implements the Union def Union(hashSet, first, second): # Find the first father first_father = Find(hashSet, first) # Find the second father second_father = Find(hashSet, second) # If both are unequals then update # first father as ssecond_father if (first_father != second_father): hashSet[first_father] = second_father # Recursive Function that change all # the corners connected 1s to 0s def change(matrix, x, y, n, m): # If already zero then return if (x < 0 or y < 0 or x > m - 1 or y > n - 1 or matrix[x][y] == '0'): return # Change the current cell to '0' matrix[x][y] = '0' # Recursive Call for all the # four corners change(matrix, x + 1, y, n, m) change(matrix, x, y + 1, n, m) change(matrix, x - 1, y, n, m) change(matrix, x, y - 1, n, m) # Function that changes all the # connected 1s to 0s at the corners def changeCorner(matrix): # Dimensions of matrix m = len(matrix) n = len(matrix[0]) # Traverse the matrix for i in range(m): for j in range(n): # If corner cell if (i * j == 0 or i == m - 1 or j == n - 1): # If value is 1s, then # recursively change to 0 if (matrix[i][j] == '1'): change(matrix, i, j, n, m) # Function that counts the number # of island in the given matrix def numIslands(matrix): if (len(matrix) == 0): return 0 # Dimensions of the matrix m = len(matrix) n = len(matrix[0]) # Make all the corners connecting # 1s to zero changeCorner(matrix) # First convert to 1 dimension # position and convert all the # connections to edges edges = [] for i in range(m): for j in range(n): # If the cell value is 1 if (matrix[i][j] == '1'): id = i * n + j # Move right if (j + 1 < n): # If right cell is # 1 then make it as # an edge if (matrix[i][j + 1] == '1'): right = i * n + j + 1 # Push in edge vector edges.append([id, right]) # Move down if (i + 1 < m): # If right cell is # 1 then make it as # an edge if (matrix[i + 1][j] == '1'): down = (i + 1) * n + j # Push in edge vector edges.append([id, down]) # Construct the Union Find structure hashSet = [0 for i in range(m*n)] for i in range(m*n): hashSet[i] = i # Next apply Union Find for all # the edges stored for edge in edges: Union(hashSet, edge[0], edge[1]) # To count the number of connected # islands numComponents = 0 # Traverse to find the islands for i in range(m*n): if (matrix[i // n][i % n] == '1' and hashSet[i] == i): numComponents += 1 # Return the count of the island return numComponents # Driver Code if __name__ == '__main__': # Given size of Matrix N = 5 M = 8 # Given Matrix matrix = [['0', '0', '0', '0', '0', '0', '0', '1'], ['0', '1', '1', '1', '1', '0', '0', '1'], ['0', '1', '0', '1', '0', '0', '0', '1'], ['0', '1', '1', '1', '1', '0', '1', '0'], ['0', '0', '0', '0', '0', '0', '0', '1']] # Function Call print(numIslands(matrix)) # This code is contributed by bgangwar59.
Javascript
<script> // JavaScript program for the above approach // Function that implements the Find function Find(hashSet, val) { // Get the val var parent = val; // Until parent is not found while (parent != hashSet[parent]) { parent = hashSet[parent]; } // Return the parent return parent; } // Function that implements the Union function Union(hashSet, first, second) { // Find the first father var first_father = Find(hashSet, first); // Find the second father var second_father = Find(hashSet, second); // If both are unequals then update // first father as ssecond_father if (first_father != second_father) { hashSet[first_father] = second_father; } } // Recursive Function that change all // the corners connected 1s to 0s function change(matrix, x, y, n, m) { // If already zero then return if (x < 0 || y < 0 || x > m - 1 || y > n - 1 || matrix[x][y] == "0") { return; } // Change the current cell to '0' matrix[x][y] = "0"; // Recursive Call for all the // four corners change(matrix, x + 1, y, n, m); change(matrix, x, y + 1, n, m); change(matrix, x - 1, y, n, m); change(matrix, x, y - 1, n, m); } // Function that changes all the // connected 1s to 0s at the corners function changeCorner(matrix) { // Dimensions of matrix var m = matrix.length; var n = matrix[0].length; // Traverse the matrix for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { // If corner cell if (i * j == 0 || i == m - 1 || j == n - 1) { // If value is 1s, then // recursively change to 0 if (matrix[i][j] == "1") { change(matrix, i, j, n, m); } } } } } // Function that counts the number // of island in the given matrix function numIslands(matrix) { if (matrix.length == 0) { return 0; } // Dimensions of the matrix var m = matrix.length; var n = matrix[0].length; // Make all the corners connecting // 1s to zero changeCorner(matrix); // First convert to 1 dimension // position and convert all the // connections to edges var edges = []; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { // If the cell value is 1 if (matrix[i][j] == "1") { id = i * n + j; // Move right if (j + 1 < n) { // If right cell is // 1 then make it as // an edge if (matrix[i][j + 1] == "1") { var right = i * n + j + 1; // Push in edge vector edges.push([id, right]); } } // Move down if (i + 1 < m) { // If right cell is // 1 then make it as // an edge if (matrix[i + 1][j] == "1") { var down = (i + 1) * n + j; // Push in edge vector edges.push([id, down]); } } } } } // Construct the Union Find structure var hashSet = Array(m * n).fill(0); for (let i = 0; i < m * n; i++) { hashSet[i] = i; } // Next apply Union Find for all // the edges stored for (let i =0; i<edges.length; i++ ) { Union(hashSet, edges[i][0], edges[i][1]); } // To count the number of connected // islands var numComponents = 0; // Traverse to find the islands for (let i = 0; i < m * n; i++) { if (matrix[parseInt(i / n)][i % n] == "1" && hashSet[i] == i) { numComponents += 1; } } // Return the count of the island return numComponents; } // Driver Code // Given size of Matrix var N = 5; var M = 8; // Given Matrix var matrix = [ ["0", "0", "0", "0", "0", "0", "0", "1"], ["0", "1", "1", "1", "1", "0", "0", "1"], ["0", "1", "0", "1", "0", "0", "0", "1"], ["0", "1", "1", "1", "1", "0", "1", "0"], ["0", "0", "0", "0", "0", "0", "0", "1"], ]; // Function Call document.write(numIslands(matrix)); // This code is contributed by rdtank. </script>
2
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)