给你一个NxM的网格,要求你添k堵墙,最后仍使所有的空地是联通的
我们可以反过来想,添k堵墙可以想成给cnt-k个空地构成的连通块打上标记,没有打上标记的即为空地
#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=505;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
char g[N][N];
bool used[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int n,m,k;
void dfs(int x,int y){
if(k==0) return;
k--;
g[x][y]='1';
for(int i=0;i<4;i++){
int gx=x+dx[i],gy=y+dy[i];
if(gx>=0 && gy>=0 && gx<n && gy<m && g[gx][gy]=='.'){
used[gx][gy]=true;
dfs(gx,gy);
}
}
}
void solve(){
cin>>n>>m>>k;
for(int i=0;i<n;i++) cin>>g[i];
int cnt=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='.') cnt++;
}
}
k=cnt-k;
int fg=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='.'){
used[i][j]=true;
dfs(i,j);
fg=1;
break;
}
}
if(fg) break;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(g[i][j]=='1') cout<<'.';
else if(g[i][j]=='.') cout<<'X';
else cout<<g[i][j];
}
cout<<endl;
}
}
int main(){
IOS;
solve();
return 0;
}