#include <bits/stdc++.h>
using namespace std;
void dfs(vector<string>&grid,int i,int j,vector<pair<int,int>>&ans){
grid[i][j] = '*';
ans.push_back({i,j});
if(i < grid.size()-1 && grid[i+1][j] == '.')
dfs(grid,i+1,j,ans);
if(j < grid[0].size()-1 && grid[i][j+1] == '.')
dfs(grid,i,j+1,ans);
if(i && grid[i-1][j] == '.')
dfs(grid,i-1,j,ans);
if(j && grid[i][j-1] == '.')
dfs(grid,i,j-1,ans);
}
bool mycomp(const vector<pair<int,int>>&a,const vector<pair<int,int>>&b){
return a.size() <= b.size();
}
int main()
{
int n,m,k;
cin >> n >> m >> k;
vector<string>grid(n);
for(int i = 0;i < n;i++)
cin >> grid[i];
vector<vector<pair<int,int>>>lake,border;
for(int i = 0;i < n;i++){
if(grid[i][0] == '.'){
vector<pair<int,int>>v;
dfs(grid,i,0,v);
border.push_back(v);
}
if(grid[i][m-1] == '.'){
vector<pair<int,int>>v;
dfs(grid,i,m-1,v);
border.push_back(v);
}
}
// cout << border.size() << "\n";
for(int j = 0;j < m;j++){
if(grid[0][j] == '.'){
vector<pair<int,int>>v;
dfs(grid,0,j,v);
border.push_back(v);
}
if(grid[n-1][j] == '.'){
vector<pair<int,int>>v;
dfs(grid,n-1,j,v);
border.push_back(v);
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(grid[i][j] == '.'){
vector<pair<int,int>>ans;
dfs(grid,i,j,ans);
lake.push_back(ans);
}
}
}
sort(lake.begin(),lake.end(),mycomp);
int ans = 0;
if(lake.size() >= k){
for(int i = 0;i < border.size();i++){
for(int j = 0;j < border[i].size();j++)
grid[border[i][j].first][border[i][j].second] = '.';
}
for(int i = 0;i < lake.size()-k;i++)
ans += lake[i].size();
for(int i = 0;i < k;i++){
for(int j = 0;j < lake[lake.size()-i-1].size();j++)
grid[lake[lake.size()-i-1][j].first][lake[lake.size()-i-1][j].second] = '.';
}
}else{
int count = lake.size();
map<int,vector<int>>mp;
for(int i = 0;i < border.size();i++){
int count1 = 0;
for(auto x:border[i]){
if(x.first == n-1 || !x.first || !x.second || x.second == m-1)
count1++;
}
mp[count1].push_back(i);
}
for(auto it = mp.begin();it != mp.end();it++){
for(auto x:it->second){
if(it->first != border[x].size() && count < k){
count++;
ans += it->first;
for(auto y:border[x]){
if(y.first != n-1 && y.first && y.second && y.second != m-1)
grid[y.first][y.second] = '.';
}
}else{
for(auto y:border[x])
grid[y.first][y.second] = '.';
}
}
}
for(auto x:lake){
for(auto y:x)
grid[y.first][y.second] = '.';
}
}
cout << ans << "\n";
for(auto &x:grid)
cout << x << "\n";
return 0;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}