Encuentre la longitud de la región más grande en Boolean Matrix

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

  1. Una celda en array 2D se puede conectar a un máximo de 8 vecinos.
  2. Entonces, en DFS, haga llamadas recursivas para 8 vecinos de esa celda.
  3. Mantenga un Hash-map visitado para realizar un seguimiento de todas las celdas visitadas.
  4. 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

  1. Si el valor en cualquier celda en particular es 1, entonces desde aquí necesitamos hacer el recorrido BFS.
  2. empuja el par<i,j> en la cola.
  3. Marcando el valor de 1 a -1 para que no volvamos a empujar la misma celda.
  4.  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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *