codeforces 377A Maze

點擊打開cf377A

題意：給定一個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;
}