题意:有n*m矩阵,’.’为空地,’#’为墙。在空地上添加k堵墙使得最后空地联通。保证有解。
思路:随便送任何一个空地走,走到不能走为止,,那么这个位置就可以设为’X’。然后回溯将路径上的空地都设为’x’。很明显最后的图是联通的。
#include<bits/stdc++.h>using namespace std;int n,m,k;char ch[501][501];int vis[501][501];void dfs(int x,int y){if(x<1||x>n||y<1||y>m||ch[x][y]!='.'||vis[x][y]) return ;vis[x][y]=1;dfs(x+1,y);dfs(x-1,y);dfs(x,y+1);dfs(x,y-1);if(k) ch[x][y]='X',k–;}int main(){int i,j;cin>>n>>m>>k;for(i=1;i<=n;i++)cin>>ch[i]+1;for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(ch[i][j]=='.'&&k) dfs(i,j);for(i=1;i<=n;i++) puts(ch[i]+1);}
通电话,旅行,重复一个承诺和梦想,