➤ Problem Link : 193A. Cutting Figure
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pp pair<int,int>
#define mp make_pair
int n,m;
char arr[51][51];
int disc[51][51];
int low[51][51];
pp parent[51][51];
int t;
bool flag;
int lt[]={-1,1,0,0};
int rt[]={0,0,-1,1};
void dfs(int i, int j, pp p)
{
if(flag)
return;
parent[i][j]=p;
disc[i][j]=++t;
low[i][j]=disc[i][j];
int x,y,child=0;
for(int k=0;k<4;k++)
{
x=i+lt[k];
y=j+rt[k];
if(x>=0 && x<n && y>=0 && y<m && arr[x][y]=='#')
{
if(mp(x,y)==p)
continue;
if(!disc[x][y])
{
child++;
dfs(x,y,mp(i,j));
low[i][j]=min(low[i][j],low[x][y]);
if(parent[i][j]!=mp(-1,-1) && low[x][y] >= disc[i][j])
{
flag=1;
return;
}
}
else
low[i][j]=min(low[i][j],disc[x][y]);
}
}
if(parent[i][j]==mp(-1,-1) && child>1) // root child tells no of subtrees not no of child
flag=1;
}
int main()
{
int cnt=0;
cin>>n>>m;
t=0,flag=0;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>arr[i][j];
if(arr[i][j]=='#')
cnt++;
}
if(cnt<3)
{
cout<<"-1";
exit(0);
}
memset(disc,0,sizeof(disc));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(arr[i][j]=='#' && !disc[i][j])
dfs(i,j,mp(-1,-1));
if(flag)
cout<<1;
else
cout<<2;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.