CodeForces 377A-Maze（DFS找连通块）

2022-06-14 142

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： CodeForces 377A-Maze（DFS找连通块）

本题的来源在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;
}