Problem Statement:
We have a binary grid containing only 0s and 1s, with 1s representing non-empty cells and 0s representing empty cells. Our objective is to identify all connected components of non-empty cells in the grid. A pair of cells are considered connected if they are adjacent either horizontally or vertically.
For Example:
Input:
- mat = {[3,1],[4,1]}
Output:
Input:
- mat = {[1,2],[2,1]}
Output:
Algorithm:
- Create a queue data structure, and then add a cell with the value cell(mati = 1).
- Go through the neighboring cells of the inserted cell and perform BFS or DFS on it.
- Verify whether there are any boundary conditions, and if the element is now 1, flip it to 0.
- Update the size of the linked non-empty cells and mark the visited cell.
- Print each side of the obtained connections at the end.
Program 1:
Let's consider a C++ code to determine the dimensions of all Connected Non-Empty Cells in a Matrix utilizing Depth-First Search traversal.
#include<iostream>
#include<vector>
using namespace std;
int rs, cs;
//Function to perform DFS traversal
void dfs(vector<vector<int>>& mat , int r, int c , vector<vector<bool>> & visit,int &s)
{
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
visit[r][c]=true;
s++;
//Explore the neighbors
for(int x=0;x<4;x++)
{
int newrow=r+dx[x];
int newcol = c+dy[x];
//check if the neighbor is within the bounds and is not visited
if(newrow>=0 && newrow<rs && newcol>=0 && newcol<cs && mat[newrow][newcol]==1 && !visit[newrow][newcol])
{
dfs(mat,newrow,newcol,visit,s);
}
}
}
//Function to find the size of all connected non-empty cells of the matrix using DFS
vector<int>findsizeDFS(vector<vector<int>>&mat)
{
vector<vector<bool>>visited(rs,vector<bool>(cs,false));
vector<int>sizes;
for(int p=0;p<rs;p++){
for(int q=0;q<cs;q++)
{
if(mat[p][q] ==1 && !visited[p][q])
{
int size=0;
dfs(mat,p,q,visited,size);
sizes.push_back(size);
}
}
}
return sizes;
}
int main()
{
//Input the matrix size
cout<<"Enter the number of rows and columns";
cin>>rs>>cs;
//Input the matrix
cout<<"Enter the matrix:\n";
vector<vector<int>>matrix(rs,vector<int>(cs));
for(int p=0;p<rs;p++)
{
for(int q=0;q<cs;q++)
{
cin>>matrix[p][q];
}
}
//Find the sizes using DFS
vector<int>sizes=findsizeDFS(matrix);
//output the sizes
cout<<"Sizes of connected non-empty cells using DFS:\n";
for(int size:sizes)
{
cout<<size<<" ";
}
cout<<endl;
return 0;
}
Output:
Time Complexity:
The computational complexity of determining the dimensions of every interconnected non-empty cell within a matrix utilizing Depth-First Search traversal is O(rs * cs).
Space Complexity:
The space complexity required to determine the sizes of all connected non-empty cells within a matrix through DFS traversal is O(rs * cs).
Program 2:
Let's explore a different C++ code example to determine the total size of all Connected Non-Empty Cells within a Matrix by employing BFS traversal:
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int rs, cs;
//Function to perform BFS traversal
void bfs(vector<vector<int>>& matrix , int r,int c , vector<vector<bool>> &visited,int & s)
{
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
queue<pair<int , int>>q;
q.push({r,c});
visited[r][c]=true;
while(!q.empty())
{
pair<int,int>current = q.front();
q.pop();
s++;
//Explore the neighbors
for(int o=0;o<4;o++)
{
int nr=current.first+dx[o];
int nc = current.second+dy[o];
//check if the neighbor is within the bounds and is not visited
if(nr>=0 && nr<rs && nc>=0 && nc<cs && matrix[nr][nc]==1 && !visited[nr][nc])
{
visited[nr][nc]=true;
}
}
}
}
//Function to find the size of all connected non-empty cells of the matrix using BFS
vector<int>findsizeBFS(vector<vector<int>>&matrix)
{
vector<vector<bool>>visited(rs,vector<bool>(cs,false));
vector<int>sizes;
for(int m=0;m<rs;m++)
{
for(int n=0;n<cs;n++)
{
if(matrix[m][n]==1 && !visited[m][n])
{
int s=0;
bfs(matrix,m,n,visited,s);
sizes.push_back(s);
}
}
}
return sizes;
}
int main()
{
//Input the matrix size
cout<<"Enter the number of rows and columns";
cin>>rs>>cs;
//Input the matrix
cout<<"Enter the matrix:\n";
vector<vector<int>>matrix(rs,vector<int>(cs));
for(int m=0;m<rs;m++)
{
for(int n=0;n<cs;n++)
{
cin>>matrix[m][n];
}
}
//find sizes using BFS
vector<int>sizes=findsizeBFS(matrix);
//output the sizes
cout<<"Sizes of connected non-empty cells using DFS:\n";
for(int size:sizes)
{
cout<<size<<" ";
}
cout<<endl;
return 0;
}
Output:
Time Complexity:
The time complexity for determining the sizes of interconnected non-empty cells in a matrix through BFS traversal is O(rs * cs).
Space Complexity:
The space complexity for determining the dimensions of all interconnected non-empty cells within a matrix through BFS traversal amounts to O(rs * cs).
Conclusion:
To summarize, it can be inferred that Breadth First Search (BFS) and Depth First Search (DFS) both offer efficient solutions with time and space complexities of O(rs*cs), where rs denotes the row count and cs denotes the column count in the matrix when evaluating the dimensions of interconnected non-empty cells within a matrix. The selection between DFS and BFS is contingent on multiple factors like memory constraints, traversal sequences, and specific problem requirements. Upon careful evaluation of these factors, both techniques prove to be effective in resolving the provided issue.
