➤ Problem Link : 723D. Lakes in Berland
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int n,m,k;
pair<int,int> parent[52][52];
int sz[52][52];
vector<pair<int,int> > v;
char arr[52][52];
bool visited[52][52];
int lr[]={-1,1,0,0};
int rr[]={0,0,1,-1};
bool comp(pair<int,int> x, pair<int,int> y)
{
return sz[x.first][x.second]<sz[y.first][y.second];
}
pair<int,int> find(int x,int y)
{
if(parent[x][y]==make_pair(x,y))
return make_pair(x,y);
return parent[x][y]=find(parent[x][y].first,parent[x][y].second);
}
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
if(x+lr[i]>1 && x+lr[i]<n && y+rr[i]>1 && y+rr[i]<m && arr[x+lr[i]][y+rr[i]]=='.' && !visited[x+lr[i]][y+rr[i]])
{
visited[x+lr[i]][y+rr[i]]=1;
pair<int,int> p1=find(x,y);
pair<int,int> p2=find(x+lr[i], y+rr[i]);
if(p1!=p2)
{
parent[p2.first][p2.second]=p1;
sz[p1.first][p1.second]+=sz[p2.first][p2.second];
}
dfs(x+lr[i],y+rr[i]);
}
}
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>arr[i][j];
}
memset(visited,0,sizeof(visited));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if((i==1 || i==n || j==1 || j==m) && !visited[i][j] && arr[i][j]=='.')
{
// cout<<i<<" "<<j<<endl;
visited[i][j]=1;
dfs(i,j);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(!visited[i][j] & arr[i][j]!='*')
{
parent[i][j]=make_pair(i,j);
sz[i][j]=1;
}
else
{
parent[i][j]=make_pair(-1,-1);
sz[i][j]=0;
}
}
}
for(int i=2;i<n;i++)
{
for(int j=2;j<m;j++)
{
if(arr[i][j]=='.' && !visited[i][j])
{
// cout<<i<<" "<<j<<endl;
visited[i][j]=1;
dfs(i,j);
}
}
}
for(int i=2;i<n;i++)
{
for(int j=2;j<m;j++)
{
if(arr[i][j]=='.' && parent[i][j]==make_pair(i,j))
v.push_back(make_pair(i,j));
}
}
sort(v.begin(),v.end(),comp);
set<pair<int,int> > st;
int tot=v.size();
tot-=k;
ll ans=0;
for(int i=0;i<tot;i++)
{
ans+=sz[v[i].first][v[i].second];
st.insert(v[i]);
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
pair<int,int> p=find(i,j);
if(st.find(p)==st.end())
cout<<arr[i][j];
else
cout<<'*';
}
cout<<"\n";
}
}
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.