首页 > 代码库 > codeforces - 377A 题解
codeforces - 377A 题解
题目大意:给定一个n*m区域,#为墙,“.”为空地,填充k片空地,同时使得剩下的空地继续保持连通
题目解法:DFS遍历sum-k片空地(sum是空地总数),然后枚举一遍,没有被遍历过的空地全部填充
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<climits> 5 #include<cstring> 6 using namespace std; 7 int map[502][502]; 8 bool vis[502][502]; 9 int n,m,k; 10 int sum=0; 11 int amount=0; 12 void dfs(int x,int y) 13 { 14 vis[x][y]=true; 15 amount+=1; 16 if(amount==sum-k) 17 { 18 return; 19 } 20 if(!vis[x-1][y]&&map[x-1][y]&&amount!=sum-k) 21 { 22 dfs(x-1,y); 23 } 24 if(!vis[x+1][y]&&map[x+1][y]&&amount!=sum-k) 25 { 26 dfs(x+1,y); 27 } 28 if(!vis[x][y-1]&&map[x][y-1]&&amount!=sum-k) 29 { 30 dfs(x,y-1); 31 } 32 if(!vis[x][y+1]&&map[x][y+1]&&amount!=sum-k) 33 { 34 dfs(x,y+1); 35 } 36 return; 37 } 38 int main() 39 { 40 41 scanf("%d%d%d",&n,&m,&k); 42 memset(map,0,sizeof(map)); 43 memset(vis,false,sizeof(vis)); 44 for(int i=1;i<=n;i++) 45 { 46 getchar(); 47 for(int j=1;j<=m;j++) 48 { 49 char c=getchar(); 50 if(c==‘#‘) 51 { 52 map[i][j]=0; 53 } 54 else 55 { 56 map[i][j]=1; 57 sum+=1; 58 } 59 } 60 } 61 for(int i=1;i<=n&&amount!=sum-k;i++) 62 { 63 for(int j=1;j<=m;j++) 64 { 65 if(map[i][j]) 66 { 67 dfs(i,j); 68 break; 69 } 70 } 71 } 72 for(int i=1;i<=n;i++) 73 { 74 for(int j=1;j<=m;j++) 75 { 76 if(!map[i][j]) 77 { 78 printf("#"); 79 } 80 else 81 { 82 if(vis[i][j]) 83 { 84 printf("."); 85 } 86 else 87 { 88 printf("X"); 89 } 90 } 91 } 92 printf("\n"); 93 } 94 return 0; 95 }
codeforces - 377A 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。