723D Codeforces - Lakes in Berland
Solution in c++
#include <bits/stdc++.h>
using namespace std;
int n,m,k,sol,gaps;
vector<string> all(51);
priority_queue<pair<int ,pair<int,int> > > sizes;
int vis[51][51];
int valid(int x,int y)
{
if(x<0 || y<0 || x>=n || y>=m)return 0;
return 1;
}
int srch(int x,int y)
{
if(vis[x][y] || all[x][y]=='*')return 0;
vis[x][y]=1;
if(all[x][y]=='.')sol++;
srch(x+1,y);
srch(x-1,y);
srch(x,y+1);
srch(x,y-1);
}
int fld(int x,int y)
{
if(!valid(x,y) || vis[x][y] || all[x][y]=='*')return 0;
vis[x][y]=1;
fld(x+1,y);
fld(x-1,y);
fld(x,y+1);
fld(x,y-1);
return 0;
}
int paint(int x,int y)
{
if(!valid(x,y) || all[x][y]=='*')return 0;
all[x][y]='*';
paint(x+1,y);
paint(x-1,y);
paint(x,y+1);
paint(x,y-1);
return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m>>k;
for(int i=0;i<n;i++)cin>>all[i];
for(int i=0;i<n;i++)
{
if(i==0 || i==n-1)
{
for(int o=0;o<m;o++)
{
if(all[i][o]=='.')fld(i,o);
}
}
else
{
fld(i,0);
fld(i,m-1);
}
}
for(int i=0;i<n;i++)
{
if(i!=0 || i!=n-1)
{
for(int o=1;o<m-1;o++)
{
if(all[i][o]=='.' && !vis[i][o])
{
sol=0;
srch(i,o);
sizes.push({-sol,{i,o} });
gaps++;
}
}
}
}
gaps-=k;
sol=0;
while(gaps--)
{
sol+=-sizes.top().first;
paint(sizes.top().second.first,sizes.top().second.second);
sizes.pop();
}
cout<<sol<<"\n";
for(int i=0;i<n;i++)
{
for(int o=0;o<m;o++)cout<<all[i][o];
cout<<"\n";
}
return 0;
}
0 التعليقات:
إرسال تعليق