codeforces|codeforces - 377A 题解 codeforces-377A题解

题目大意：给定一个n*m区域，#为墙，“.”为空地，填充k片空地，同时使得剩下的空地继续保持连通
题目解法：DFS遍历sum-k片空地（sum是空地总数），然后枚举一遍，没有被遍历过的空地全部填充

1 #include 2 #include 3 #include 4 #include 5 #include 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 { 14vis[x][y]=true; 15amount+=1; 16if(amount==sum-k) 17{ 18return; 19} 20if(!vis[x-1][y]&&map[x-1][y]&&amount!=sum-k) 21{ 22dfs(x-1,y); 23} 24if(!vis[x+1][y]&&map[x+1][y]&&amount!=sum-k) 25{ 26dfs(x+1,y); 27} 28if(!vis[x][y-1]&&map[x][y-1]&&amount!=sum-k) 29{ 30dfs(x,y-1); 31} 32if(!vis[x][y+1]&&map[x][y+1]&&amount!=sum-k) 33{ 34dfs(x,y+1); 35} 36return; 37 } 38 int main() 39 { 40 41scanf("%d%d%d",&n,&m,&k); 42memset(map,0,sizeof(map)); 43memset(vis,false,sizeof(vis)); 44for(int i=1; i<=n; i++) 45{ 46getchar(); 47for(int j=1; j<=m; j++) 48{ 49char c=getchar(); 50if(c=='#') 51{ 52map[i][j]=0; 53} 54else 55{ 56map[i][j]=1; 57sum+=1; 58} 59} 60} 61for(int i=1; i<=n&&amount!=sum-k; i++) 62{ 63for(int j=1; j<=m; j++) 64{ 65if(map[i][j]) 66{ 67dfs(i,j); 68break; 69} 70} 71} 72for(int i=1; i<=n; i++) 73{ 74for(int j=1; j<=m; j++) 75{ 76if(!map[i][j]) 77{ 78printf("#"); 79} 80else 81{ 82if(vis[i][j]) 83{ 84printf("."); 85} 86else 87{ 88printf("X"); 89} 90} 91} 92printf("\n"); 93} 94return 0; 95 }

【codeforces|codeforces - 377A 题解】转载于:https://www.cnblogs.com/shao0099876/p/7344330.html