题意：给出n*m的矩阵，矩阵由'.'和'#'组成，再给出k，表示需要在'.'处加k堵墙，使得剩下的'.'仍然是连通的
先统计出这个矩阵里面总的点数'.'为sum
因为题目说了一定会有一个解，所以找到一个'.',就开始搜，搜到sum-k个连通的点的时候跳出，剩下的没有访问过的点就全部填成墙
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=1005; 17 18 char g[maxn][maxn]; 19 int vis[maxn][maxn]; 20 int ans,n,m,k,cnt; 21 int dir[4][2]={1,0,-1,0,0,1,0,-1}; 22 23 void dfs(int x,int y){ 24 vis[x][y]=1; 25 cnt++; 26 if(cnt==ans) return; 27 for(int i=0;i<4;i++){ 28 if(cnt==ans) return; 29 int xx=x+dir[i][0]; 30 int yy=y+dir[i][1]; 31 if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]||g[xx][yy]!='.') continue; 32 dfs(xx,yy); 33 } 34 } 35 36 int main(){ 37 scanf("%d %d %d",&n,&m,&k); 38 for(int i=1;i<=n;i++) 39 for(int j=1;j<=m;j++) cin>>g[i][j]; 40 41 ans=0; 42 for(int i=1;i<=n;i++){ 43 for(int j=1;j<=m;j++){ 44 if(g[i][j]=='.') ans++; 45 } 46 } 47 ans=ans-k; 48 49 for(int i=1;i<=n;i++){ 50 int flag=0; 51 for(int j=1;j<=m;j++){ 52 cnt=0; 53 if(g[i][j]=='.'){ 54 dfs(i,j); 55 flag=1; 56 break; 57 } 58 } 59 if(flag) break; 60 } 61 62 for(int i=1;i<=n;i++){ 63 for(int j=1;j<=m;j++){ 64 if(g[i][j]=='.'&&!vis[i][j]) g[i][j]='X'; 65 } 66 } 67 68 69 for(int i=1;i<=n;i++){ 70 for(int j=1;j<=m;j++) 71 printf("%c",g[i][j]); 72 printf(" "); 73 } 74 return 0; 75 }