CodeFoeces-377A

题目

原题链接:A. Maze

题意

给出一个n*m的表,#表示墙,.表示路。现要填充k个X。要求填充后的路也是一个整体。
参考了其他作者的思路。利用dfs。如果需要填充k个,有t个路,那么只要不填充t-k个就可以。

代码

#include<bits/stdc++.h>
using namespace std;
char s[505][505];
int vis[505][505]={0};
int mov[4][2]={0,1,0,-1,1,0,-1,0};
int n,m,k,t=0;
void dfs(int r,int c){
    if(!t) return ;
    t--;
    vis[r][c]=1;
    for(int i=0;i<4;i++){
        int ti=r+mov[i][0];
        int tj=c+mov[i][1];
        if(ti>=0 && ti<n && tj>=0 && tj<m && !vis[ti][tj] && s[ti][tj]=='.'){
            dfs(ti,tj);
        }
    }
}
int main() {
    scanf("%d%d%d\n",&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]=='.'){
                t++;
            }
        }
        getchar();
    }
    t-=k;
    int flag=1;
    for(int i=0;i<n && flag;i++){
        for(int j=0;j<m && flag;j++){
            if(s[i][j]=='.') {
                dfs(i,j);
                flag=0;
            } 
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='.' && !vis[i][j]) {
                printf("X");
            } else{
                printf("%c",s[i][j]);
            }
        }
        printf("\n");
    }
    return 0;
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,778评论 0 33
  • 这个不错分享给大家,从扣上看到的,就转过来了 《电脑专业英语》 file [fail] n. 文件;v. 保存文...
    麦子先生R阅读 6,620评论 5 24
  • 一年级语文上册生字表 生字表一(共400字) 啊(ā)爱(ài)安(ān)岸(àn)爸(bà)八(bā)巴(bā)...
    meychang阅读 2,888评论 0 6
  • 月亮升起来,轻轻地 一把琴,两根弦 寂寞在指间流淌 讲述着一次凄婉的相遇 无法看到月亮的模样 拖着疲惫的身心 行...
    欣黎阅读 458评论 0 0
  • 当我还是小孩子 门前有许多的茉莉花 散发着淡淡的清香 当我渐渐地长大 门前的那些茉莉花 已经慢慢地枯萎不再萌芽 什...
    禅园听雪阅读 311评论 0 0