Considere una array con filas y columnas, donde cada celda contiene un ‘0’ o un ‘1’ y cualquier celda que contiene un 1 se denomina celda llena. Se dice que dos celdas están conectadas si están adyacentes entre sí horizontal, vertical o diagonalmente. Si una o más celdas llenas también están conectadas, forman una región. encontrar la longitud de la región más grande.
Ejemplos:
Input : M[][5] = { 0 0 1 1 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 1 } Output : 6 In the following example, there are 2 regions one with length 1 and the other as 6. So largest region: 6 Input : M[][5] = { 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 } Output: 4 In the following example, there are 2 regions one with length 1 and the other as 4. So largest region: 4
Preguntado en: entrevista de Amazon
Solución: La idea se basa en el problema o encontrar el número de islas en la array booleana 2D
Enfoque 1: uso de DFS
- Una celda en array 2D se puede conectar a un máximo de 8 vecinos.
- Entonces, en DFS, haga llamadas recursivas para 8 vecinos de esa celda.
- Mantenga un Hash-map visitado para realizar un seguimiento de todas las celdas visitadas.
- También realice un seguimiento de los 1 visitados en cada DFS y actualice la región de longitud máxima.
A continuación se muestra la implementación de la idea anterior.
C++
// Program to find the length of the largest // region in boolean 2D-matrix #include <bits/stdc++.h> using namespace std; #define ROW 4 #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], int& count) { // 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)) { // Increment region length by one count++; DFS(M, row + rowNbr[k], col + colNbr[k], visited, count); } } } // The main function that returns // largest length region // of a given boolean 2D matrix int largestRegion(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 result as 0 and travesle through the // all cells of given matrix int result = INT_MIN; 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 region found int count = 1; DFS(M, i, j, visited, count); // maximum region result = max(result, count); } } } return result; } // Driver code int main() { int M[][COL] = { { 0, 0, 1, 1, 0 }, { 1, 0, 1, 1, 0 }, { 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1 } }; // Function call cout << largestRegion(M); return 0; }
Java
// Java program to find the length of the largest // region in boolean 2D-matrix import java.io.*; import java.util.*; class GFG { static int ROW, COL, count; // A function to check if a given cell (row, col) // can be included in DFS static 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 neighbours as // adjacent vertices static void DFS(int[][] M, int row, int col, boolean[][] visited) { // These arrays are used to get row and column // numbers of 8 neighbours of a given cell int[] rowNbr = { -1, -1, -1, 0, 0, 1, 1, 1 }; 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)) { // increment region length by one count++; DFS(M, row + rowNbr[k], col + colNbr[k], visited); } } } // The main function that returns largest length region // of a given boolean 2D matrix static int largestRegion(int[][] M) { // Make a boolean array to mark visited cells. // Initially all cells are unvisited boolean[][] visited = new boolean[ROW][COL]; // Initialize result as 0 and traverse through the // all cells of given matrix int result = 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] == 1 && !visited[i][j]) { // visited yet, then new region found count = 1; DFS(M, i, j, visited); // maximum region result = Math.max(result, count); } } } return result; } // Driver code public static void main(String args[]) { int M[][] = { { 0, 0, 1, 1, 0 }, { 1, 0, 1, 1, 0 }, { 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1 } }; ROW = 4; COL = 5; // Function call System.out.println(largestRegion(M)); } } // This code is contributed by rachana soma
Python3
# Python3 program to find the length of the # largest region in boolean 2D-matrix # A function to check if a given cell # (row, col) can be included in DFS def 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) and (row < ROW) and (col >= 0) and (col < COL) and (M[row][col] and not visited[row][col])) # A utility function to do DFS for a 2D # boolean matrix. It only considers # the 8 neighbours as adjacent vertices def DFS(M, row, col, visited, count): # 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[row][col] = True # Recur for all connected neighbours for k in range(8): if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited)): # increment region length by one count[0] += 1 DFS(M, row + rowNbr[k], col + colNbr[k], visited, count) # The main function that returns largest # length region of a given boolean 2D matrix def largestRegion(M): global ROW, COL # Make a bool array to mark visited cells. # Initially all cells are unvisited visited = [[0] * COL for i in range(ROW)] # Initialize result as 0 and traverse # through the all cells of given matrix result = -999999999999 for i in range(ROW): for j in range(COL): # If a cell with value 1 is not if (M[i][j] and not visited[i][j]): # visited yet, then new region found count = [1] DFS(M, i, j, visited, count) # maximum region result = max(result, count[0]) return result # Driver Code ROW = 4 COL = 5 M = [[0, 0, 1, 1, 0], [1, 0, 1, 1, 0], [0, 1, 0, 0, 0], [0, 0, 0, 0, 1]] # Function call print(largestRegion(M)) # This code is contributed by PranchalK
C#
// C# program to find the length of // the largest region in boolean 2D-matrix using System; class GFG { static int ROW, COL, count; // A function to check if a given cell // (row, col) can be included in DFS static 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 neighbours as // adjacent vertices static void DFS(int[, ] M, int row, int col, Boolean[, ] visited) { // These arrays are used to get row and column // numbers of 8 neighbours of a given cell int[] rowNbr = { -1, -1, -1, 0, 0, 1, 1, 1 }; 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)) { // increment region length by one count++; DFS(M, row + rowNbr[k], col + colNbr[k], visited); } } } // The main function that returns // largest length region of // a given boolean 2D matrix static int largestRegion(int[, ] M) { // Make a boolean array to mark visited cells. // Initially all cells are unvisited Boolean[, ] visited = new Boolean[ROW, COL]; // Initialize result as 0 and traverse // through the all cells of given matrix int result = 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] == 1 && !visited[i, j]) { // visited yet, // then new region found count = 1; DFS(M, i, j, visited); // maximum region result = Math.Max(result, count); } } } return result; } // Driver code public static void Main(String[] args) { int[, ] M = { { 0, 0, 1, 1, 0 }, { 1, 0, 1, 1, 0 }, { 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1 } }; ROW = 4; COL = 5; // Function call Console.WriteLine(largestRegion(M)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // JavaScript program to find the length of the largest // region in boolean 2D-matrix let ROW, COL, count; // 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 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 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)) { // increment region length by one count++; DFS(M, row + rowNbr[k], col + colNbr[k], visited); } } } // The main function that returns largest length region // of a given boolean 2D matrix function largestRegion(M) { // Make a boolean 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 j=0;j<COL;j++) { visited[i][j]=false; } } // Initialize result as 0 and traverse through the // all cells of given matrix let result = 0; for (let i = 0; i < ROW; i++) { for (let j = 0; j < COL; j++) { // If a cell with value 1 is not if (M[i][j] == 1 && !visited[i][j]) { // visited yet, then new region found count = 1; DFS(M, i, j, visited); // maximum region result = Math.max(result, count); } } } return result; } // Driver code let M=[[ 0, 0, 1, 1, 0 ], [ 1, 0, 1, 1, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ] ]; ROW = 4; COL = 5; // Function call document.write(largestRegion(M)); // This code is contributed by avanitrachhadiya2155 </script>
6
Análisis de Complejidad:
- Complejidad temporal: O(ROW * COL).
En el peor de los casos, se visitarán todas las celdas, por lo que la complejidad del tiempo es O (ROW * COL). - Espacio Auxiliar: O(ROW * COL).
Para almacenar los Nodes visitados se necesita espacio O(ROW * COL).
Enfoque 2: Uso de BFS
- Si el valor en cualquier celda en particular es 1, entonces desde aquí necesitamos hacer el recorrido BFS.
- empuja el par<i,j> en la cola.
- Marcando el valor de 1 a -1 para que no volvamos a empujar la misma celda.
- Verificaremos en las 8 direcciones y si encontramos la celda que tiene el valor 1, la empujaremos a la cola y marcaremos la celda en -1.
C++
#include<bits/stdc++.h> using namespace std; //Function to find unit area of the largest region of 1s. int largestRegion(vector<vector<int>>& grid) { int m=grid.size(); int n=grid[0].size(); // creating a queue that will help in bfs traversal queue<pair<int,int>> q; int area=0; int ans=0; for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { // if the value at any particular cell is 1 then from here we need to do the BFS traversal if(grid[i][j]==1) { ans=0; // pushing the pair<i,j> in the queue q.push(make_pair(i,j)); // marking the value 1 to -1 so that we don't again push this cell in the queue grid[i][j]=-1; while(!q.empty()) { pair<int,int> t=q.front(); q.pop(); ans++; int x=t.first; int y=t.second; // now we will check in all 8 directions if(x+1<m){ if(grid[x+1][y]==1) { q.push(make_pair(x+1,y)); grid[x+1][y]=-1; } } if(x-1>=0){ if(grid[x-1][y]==1) { q.push(make_pair(x-1,y)); grid[x-1][y]=-1; } } if(y+1<n){ if(grid[x][y+1]==1) { q.push(make_pair(x,y+1)); grid[x][y+1]=-1; } } if(y-1>=0){ if(grid[x][y-1]==1) { q.push(make_pair(x,y-1)); grid[x][y-1]=-1; } } if(x+1<m && y+1<n){ if(grid[x+1][y+1]==1) { q.push(make_pair(x+1,y+1)); grid[x+1][y+1]=-1; } } if(x-1>=0 && y+1<n){ if(grid[x-1][y+1]==1) { q.push(make_pair(x-1,y+1)); grid[x-1][y+1]=-1; } } if(x-1>=0 && y-1>=0) { if(grid[x-1][y-1]==1) { q.push(make_pair(x-1,y-1)); grid[x-1][y-1]=-1; } } if(x+1<m && y-1>=0) { if(grid[x+1][y-1]==1) { q.push(make_pair(x+1,y-1)); grid[x+1][y-1]=-1; } } } area=max(ans,area); ans=0; } } } return area; } //Driver Code Starts. int main(){ vector<vector<int>> M = { { 0, 0, 1, 1, 0 }, { 1, 0, 1, 1, 0 }, { 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1 } }; // Function call cout << largestRegion(M); return 0; }
6
Análisis de Complejidad:
Complejidad temporal: O(ROW * COL).
En el peor de los casos, se visitarán todas las celdas, por lo que la complejidad del tiempo es O (ROW * COL).
Espacio Auxiliar: O(ROW * COL).
Para almacenar los Nodes visitados se necesita espacio O(ROW * COL).
Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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