Size of all connected non-empty cells of a Matrix
Given a binary matrix mat[][], the task is to find the size of all possible non-empty connected cells. An empty cell is denoted by 0 while a non-empty cell is denoted by 1.
Two cells are said to be connected if they are adjacent to each other horizontally or vertically, i.e. mat[i][j] = mat[i][j – 1] or mat[i][j] = mat[i][j + 1] or mat[i][j] = mat[i – 1][j] or mat[i][j] = mat[i + 1][j].
Examples:
Input: mat[][] = {{1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 1}}
Output: 3 3 1 1 1 1
Explanation:
{mat[0][0], mat[0][1], mat[1][1]}, {mat[1][4], mat[2][3], mat[2][4]}}, {mat[2][0]}, {mat[4][0]}, {mat[4][2]}, {mat[4[4]} are the only possible connections.1 1 0 0 0
0 1 0 0 1
1 0 0 1 1
0 0 0 0 0
1 0 1 0 1
Input: mat[][] = {{1, 1, 0, 0, 0}, {1, 1, 0, 1, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 1}}
Output: 5 4 3
- Initialize a Queue Data Structure and insert a cell(mat[i][j] = 1).
- Perform BFS on the inserted cell and traverse its adjacent cells.
- Check for boundary conditions and check if the current element is 1, then flip it to 0.
- Mark the cell visited and update the size of the connected non-empty cells.
- Finally, print all the sizes of the connections obtained.
Below is the implementation of the above approach:
C++14
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to find size of all the // islands from the given matrix int BFS(vector<vector< int > >& matrix, int row, int col) { int area = 0; // Initialize a queue for // the BFS traversal queue<pair< int , int > > Q; Q.push({ row, col }); // Iterate until the // queue is empty while (!Q.empty()) { // Top element of queue auto it = Q.front(); // Pop the element Q.pop(); int r = it.first, c = it.second; // Check for boundaries if (r < 0 || c < 0 || r > 4 || c > 4) continue ; // Check if current element is 0 if (matrix[r] == 0) continue ; // Check if current element is 1 if (matrix[r] == 1) { // Mark the cell visited matrix[r] = 0; // Incrementing the size area++; } // Traverse all neighbors Q.push({ r + 1, c }); Q.push({ r - 1, c }); Q.push({ r, c + 1 }); Q.push({ r, c - 1 }); } // Return the answer return area; } // Function to print size of each connections void sizeOfConnections(vector<vector< int > > matrix) { // Stores the size of each // connected non-empty vector< int > result; for ( int row = 0; row < 5; ++row) { for ( int col = 0; col < 5; ++col) { // Check if the cell is // non-empty if (matrix[row][col] == 1) { // Function call int area = BFS(matrix, row, col); result.push_back(area); } } } // Print the answer for ( int val : result) cout << val << " " ; } // Driver Code int main() { vector<vector< int > > matrix = { { 1, 1, 0, 0, 0 }, { 1, 1, 0, 1, 1 }, { 1, 0, 0, 1, 1 }, { 1, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1 } }; sizeOfConnections(matrix); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; import java.lang.*; class GFG{ static class pair { int first, second; pair( int first, int second) { this .first = first; this .second = second; } } // Function to find size of all the // islands from the given matrix static int BFS( int [][] matrix, int row, int col) { int area = 0 ; // Initialize a queue for // the BFS traversal Queue<pair> Q = new LinkedList<>(); Q.add( new pair(row, col)); // Iterate until the // queue is empty while (!Q.isEmpty()) { // Top element of queue pair it = Q.peek(); // Pop the element Q.poll(); int r = it.first, c = it.second; // Check for boundaries if (r < 0 || c < 0 || r > 4 || c > 4 ) continue ; // Check if current element is 0 if (matrix[r] == 0 ) continue ; // Check if current element is 1 if (matrix[r] == 1 ) { // Mark the cell visited matrix[r] = 0 ; // Incrementing the size area++; } // Traverse all neighbors Q.add( new pair(r + 1 , c)); Q.add( new pair(r - 1 , c)); Q.add( new pair(r, c + 1 )); Q.add( new pair(r, c - 1 )); } // Return the answer return area; } // Function to print size of each connections static void sizeOfConnections( int [][] matrix) { // Stores the size of each // connected non-empty ArrayList<Integer> result = new ArrayList<>(); for ( int row = 0 ; row < 5 ; ++row) { for ( int col = 0 ; col < 5 ; ++col) { // Check if the cell is // non-empty if (matrix[row][col] == 1 ) { // Function call int area = BFS(matrix, row, col); result.add(area); } } } // Print the answer for ( int val : result) System.out.print(val + " " ); } // Driver code public static void main (String[] args) { int [][] matrix = { { 1 , 1 , 0 , 0 , 0 }, { 1 , 1 , 0 , 1 , 1 }, { 1 , 0 , 0 , 1 , 1 }, { 1 , 0 , 0 , 0 , 0 }, { 0 , 0 , 1 , 1 , 1 } }; sizeOfConnections(matrix); } } // This code is contributed by offbeat |
Python3
# Python3 program to implement # the above approach from collections import deque # Function to find size of all the # islands from the given matrix def BFS(matrix, row, col): area = 0 # Initialize a queue for # the BFS traversal Q = deque() Q.append([row, col]) # Iterate until the # queue is empty while ( len (Q) > 0 ): # Top element of queue it = Q.popleft() # Pop the element # Q.pop(); r, c = it[ 0 ], it[ 1 ] # Check for boundaries if (r < 0 or c < 0 or r > 4 or c > 4 ): continue # Check if current element is 0 if (matrix[r] = = 0 ): continue # Check if current element is 1 if (matrix[r] = = 1 ): # Mark the cell visited matrix[r] = 0 # Incrementing the size area + = 1 # Traverse all neighbors Q.append([r + 1 , c]) Q.append([r - 1 , c]) Q.append([r, c + 1 ]) Q.append([r, c - 1 ]) # Return the answer return area # Function to prsize of each connections def sizeOfConnections(matrix): # Stores the size of each # connected non-empty result = [] for row in range ( 5 ): for col in range ( 5 ): # Check if the cell is # non-empty if (matrix[row][col] = = 1 ): # Function call area = BFS(matrix, row, col) result.append(area) # Print the answer for val in result: print (val, end = " " ) # Driver Code if __name__ = = '__main__' : matrix = [[ 1 , 1 , 0 , 0 , 0 ], [ 1 , 1 , 0 , 1 , 1 ], [ 1 , 0 , 0 , 1 , 1 ], [ 1 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 1 , 1 , 1 ]] sizeOfConnections(matrix) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; using System.Collections; using System.Collections.Generic; class GFG { class pair { public int first, second; public pair( int first, int second) { this .first = first; this .second = second; } } // Function to find size of all the // islands from the given matrix static int BFS( int [, ] matrix, int row, int col) { int area = 0; // Initialize a queue for // the BFS traversal Queue<pair> Q = new Queue<pair>(); Q.Enqueue( new pair(row, col)); // Iterate until the // queue is empty while (Q.Count != 0) { // Top element of queue pair it = Q.Peek(); // Pop the element Q.Dequeue(); int r = it.first, c = it.second; // Check for boundaries if (r < 0 || c < 0 || r > 4 || c > 4) continue ; // Check if current element is 0 if (matrix[r, c] == 0) continue ; // Check if current element is 1 if (matrix[r, c] == 1) { // Mark the cell visited matrix[r, c] = 0; // Incrementing the size area++; } // Traverse all neighbors Q.Enqueue( new pair(r + 1, c)); Q.Enqueue( new pair(r - 1, c)); Q.Enqueue( new pair(r, c + 1)); Q.Enqueue( new pair(r, c - 1)); } // Return the answer return area; } // Function to print size of each connections static void sizeOfConnections( int [, ] matrix) { // Stores the size of each // connected non-empty ArrayList result = new ArrayList(); for ( int row = 0; row < 5; ++row) { for ( int col = 0; col < 5; ++col) { // Check if the cell is // non-empty if (matrix[row, col] == 1) { // Function call int area = BFS(matrix, row, col); result.Add(area); } } } // Print the answer foreach ( int val in result) Console.Write(val + " " ); } // Driver code public static void Main( string [] args) { int [, ] matrix = { { 1, 1, 0, 0, 0 }, { 1, 1, 0, 1, 1 }, { 1, 0, 0, 1, 1 }, { 1, 0, 0, 0, 0 }, { 0, 0, 1, 1, 1 } }; sizeOfConnections(matrix); } } // This code is contributed by grand_master |
Javascript
<script> // Javascript program to implement // the above approach class pair { constructor(first, second) { this .first = first; this .second = second; } } // Function to find size of all the // islands from the given matrix function BFS(matrix, row, col) { var area = 0; // Initialize a queue for // the BFS traversal var Q = []; Q.push( new pair(row, col)); // Iterate until the // queue is empty while (Q.length != 0) { // Top element of queue var it = Q[0]; // Pop the element Q.shift(); var r = it.first, c = it.second; // Check for boundaries if (r < 0 || c < 0 || r > 4 || c > 4) continue ; // Check if current element is 0 if (matrix[r][ c] == 0) continue ; // Check if current element is 1 if (matrix[r] == 1) { // Mark the cell visited matrix[r] = 0; // Incrementing the size area++; } // Traverse all neighbors Q.push( new pair(r + 1, c)); Q.push( new pair(r - 1, c)); Q.push( new pair(r, c + 1)); Q.push( new pair(r, c - 1)); } // Return the answer return area; } // Function to print size of each connections function sizeOfConnections(matrix) { // Stores the size of each // connected non-empty var result = []; for ( var row = 0; row < 5; ++row) { for ( var col = 0; col < 5; ++col) { // Check if the cell is // non-empty if (matrix[row][col] == 1) { // Function call var area = BFS(matrix, row, col); result.push(area); } } } // Print the answer for ( var val of result) document.write(val + " " ); } // Driver code var matrix = [ [ 1, 1, 0, 0, 0 ], [ 1, 1, 0, 1, 1 ], [ 1, 0, 0, 1, 1 ], [ 1, 0, 0, 0, 0 ], [ 0, 0, 1, 1, 1 ] ]; sizeOfConnections(matrix); </script> |
6 4 3
Time Complexity: O(row * col)
Auxiliary Space: O(row * col)
Contact Us