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>
Producción
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;
}
Producción
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