本题的来源在CodeForces上，题目是英文，在洛谷上面直接给出了题目翻译，如下：👇👇👇
题意翻译：
题目描述：
小P非常的喜欢方格迷宫。方格迷宫是一个n*m的由墙和空地构成的长方形方阵。只有当两点满足四联通条件时才能走过去。
小P画了一个迷宫，里面所有的空地都是四连通的。但闲着没事干的小P认为自己画的迷宫里小墙太多了很难看，所以他希望能够通过把迷宫中k个格子从空地变成墙但不破坏整张图的连通性（即仍然保持所有空地在一个四连通块中）
但是小P太蠢了做不来，请你帮助他。
输入： 第一行n,m,k（描述如题） 第二到n+1行： 每行m个字符，分别是'.'或'#'。 '.'表示空地，'#'表示墙。 输出： 把整张图原样打出来，但是被你修改的格子输出'X'。
样例输入1：
3 4 2
#..#
..#.
#...
样例输出1：
#.X#
X.#.
#...
样例输入2：
5 4 5
#...
#.#.
.#..
...#
.#.#
样例输出2：
#XXX
#X#.
X#..
...#
.#.#
解题思路：
根据题目翻译，我们可以这样考虑：题目要求将原图中的 k 个 '.' 修改为 'X' ，并且保证原图的连通性。我们可以先将原图中的空地数目计算出来，然后把这些空地全部修改为 'X' ，之后开始搜索，在地图中如果找到了某一条路径是连通的，那么我们就把这条路径上的 'X' 再全部修改为 '.' 就可以了！！！仔细思考一下，你会发现这道题的输出结果并不唯一！！！
AC Code：
#include<bits/stdc++.h> using namespace std; #define N 501 char s[N][N];//存入地图的数组 int n,m,k,ans,sum,num; int dx[]={0,0,1,-1};//这两个是方向数组 int dy[]={1,-1,0,0}; bool judge(int x,int y) {//越界判断的函数 if(x>=0&&x<n&&y>=0&&y<m) return true; return false; } void dfs(int x,int y) { if(sum==ans) {//将所有空地都更换完，此时已连通！！！ return ; } s[x][y]='.';//将搜索过的围墙换成空地 sum++;//记录空地的数目 for(int i=0;i<4;i++) {//四个方向去搜索连通块 int tx=x+dx[i]; int ty=y+dy[i]; if(judge(tx,ty)&&s[tx][ty]=='X') {//不越界并且这个点是之前修改过的围墙 dfs(tx,ty);//继续下一个点去搜索连通块 } } } int main() { scanf("%d %d %d",&n,&m,&k); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf(" %c",&s[i][j]);//%前面的空格确保输入完整 if(s[i][j]=='#') { num++;//记录一下围墙的数量 } if(s[i][j]=='.') {//将地图中'.'都换成'X' s[i][j]='X'; } } } ans=n*m-num-k;//地图总数减去围墙数量，再减去需要更换的k的数量 //即ans表示的是空地数量 for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(s[i][j]=='X') { dfs(i,j);//随便找一个点开始搜索连通块 } } } for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { printf("%c",s[i][j]);//打印更新过的地图 } printf("\n"); } return 0; }
