Problem Statement:
We are given a binary matrix, which indicates that there will be only two elements present in the matrix either zero (0) or one (1), where a non-empty cell is represented by one (1) and an empty cell by zero (0). Finding every possible connected non-empty cell component is our task. Two cells must be adjacent in either a horizontal or vertical direction for them to be referred to as linked.
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 us take a C++ program to find the size of all Connected Non-Empty Cells of a Matrix using DFS 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 time complexity to find the sizes of all connected non-empty cells of a matrix using DFS traversal is O(rs * cs).
Space Complexity:
The space complexity to find the sizes of all connected non-empty cells of a matrix using DFS traversal is O(rs * cs).
Program 2:
Let us take another C++ program to find the size of all Connected Non-Empty Cells of a Matrix using 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 to find the sizes of all connected non-empty cells of a matrix using BFS traversal is O(rs * cs).
Space Complexity:
The space complexity to find the sizes of all connected non-empty cells of a matrix using BFS traversal is O(rs * cs).
Conclusion:
In summary, we can conclude that both Breadth First Search (BFS) and Depth First Search (DFS) provide effective and efficient solutions with the time and space complexities of O(rs*cs). Here, rs represents the number of rows, and cs represents the number of columns in the matrix for determining the sizes of all connected non-empty cells of a matrix. The decision for choosing between DFS and BFS depends on various factors, such as memory limitations, traversal orders, and problem specifications. After considering all the factors, both approaches are efficient for solving the given problem.