点击打开cf377A
【codeforces|codeforces 377A Maze】题意：给定一个n*m的地图，这个地图初始化有s个空地，并且这s个空地是连通的。现在要求找到一种方案放k个的墙到这个地图使得剩下的s-k个点还是连通的
思路：因为初始化的地图是一个连通的，要求s-k个点也是连通的。那么我们只要对这个图搜索到s-k个连通的点，然后剩下的k个点全部放墙就可以了
代码：
#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 510;
int n , m , s , k;
char mat[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
bool isOk(int x , int y){
if(x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && mat[x][y] == '.')
return true;
return false;
}void dfs(int x , int y){
if(k == 0)
return;
k--;
mat[x][y] = '1';
for(int i = 0 ;
i < 4 ;
i++){
int tx = x+dir[i][0];
int ty = y+dir[i][1];
if(isOk(tx,ty)){
vis[tx][ty] = true;
dfs(tx , ty);
}
}
}void output(){
for(int i = 0 ;
i < n ;
i++){
for(int j = 0 ;
j < m ;
j++){
if(mat[i][j] == '1')
printf(".");
else if(mat[i][j] == '.')
printf("X");
else
printf("%c" , mat[i][j]);
}
puts("");
}
}void solve(){
memset(vis , false , sizeof(vis));
k = s-k;
for(int i = 0 ;
i < n ;
i++){
for(int j = 0 ;
j < m ;
j++){
if(mat[i][j] == '.'){
vis[i][j] = true;
dfs(i , j);
output();
return;
}
}
}
}int main(){
scanf("%d%d%d%*c" , &n , &m , &k);
s = 0;
for(int i = 0 ;
i < n ;
i++){
gets(mat[i]);
for(int j = 0 ;
j < m ;
j++)
if(mat[i][j] == '.')
s++;
}
solve();
return 0;
} 
