O's and X's. The task is to find the number of 'X' total shapes. 'X' shape consists of one or more adjacent X's (diagonals not included).Example:
Input:
2
4 7
OOOOXXO OXOXOOX XXXXOXO OXXXOOO
10 3
XXO OOX OXO OOO XOX XOX OXO XXO XXX OOO
Output:
4
6
Explanation:
Testcase 1: Given input is like:
OOOOXXO
OXOXOOX
XXXXOXO
OXXXOOO
So, X with same color is adjacent to each other vertically for horizontally (diagonals not included). So, there are 4 different groups in the given matrix.
Testcase 2: Given input is like:
XXO
OOX
OXO
OOO
XOX
XOX
OXO
XXO
XXX
OOO
So, this matrix has 6 groups with is having adjacent Xs. Total number of groups is 6
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> dir={{0,1},{1,0},{0,-1},{-1,0}};
void BFS(vector< vector<char> > & a,int n,int m,int x,int y)
{
if(x<0||y<0||x>=n||y>=m ||a[x][y]!='X')
return ;
a[x][y]='V';
for(int i=0;i<4;++i)
{
BFS(a,n,m,dir[i].first+x,dir[i].second+y);
}
}
int main() {
//code
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
vector< vector<char> > a(n,vector<char>(m));
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
cin>>a[i][j];
}
}
int cnt =0;
for(int i=0;i<n;++i)
{
for(int j=0;j<m;++j)
{
if(a[i][j]=='X')
{
cnt++;
BFS(a,n,m,i,j);
}
}
}
cout<<cnt<<endl;
}
return 0;
}
