M. Camouflage (搜索)

46 阅读 0 评论 31 点赞

我是靠谱客的博主成就小霸王，最近开发中收集的这篇文章主要介绍M. Camouflage (搜索)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

从外层开始搜，标记哪些在外围的点

找到内层的点，记录要涂的点数，合适就填上。

// Problem: M. Camouflage
// Contest: Codeforces - The 15-th BIT Campus Programming Contest - Onsite Round
// URL: https://codeforces.com/gym/102878/problem/M
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
using namespace std;
#define ff first
#define ss second
#define lowbit(x) (x&-x)
#define pf(a) printf("%dn",a)
#define mem(x,y) memset(x,y,sizeof(x))
#define dbg(x) cout << #x << " = " << x << endl
#define rep(i,l,r) for(int i = l; i <= r; i++)
#define fep(i,a,b) for(int i=b; i>=a; --i)
typedef pair<int,int> PII;
typedef long long ll;


const int N=1e3+100;
int n, m, d;
bool vis[N][N];
char maze[N][N];

int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1}; 

void bfs()
{
	queue <PII> q;
	
	q.push({0,0});
	
	while(q.size())
	{
		auto t = q.front();
		
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			int x = t.ff+dx[i], y = t.ss+dy[i];
			if(x>n+1 or x < 0 or y>m+1 or y < 0) continue;
			if(vis[x][y]) continue;
			if(maze[x][y]=='.')
			{
				vis[x][y] = true;
				q.push({x,y});
			}
		}
		
	}
}

void Bfs(int xx, int yy)
{
	queue<PII> q;
	q.push({xx,yy});
	vis[xx][yy] = true;
	vector<PII> v;
	v.push_back({xx,yy});
	int cnt = 1;
	while(q.size())
	{
		auto t = q.front();
		q.pop();
		for(int i = 0; i < 4; i++)
		{
			int x = t.ff+dx[i], y = t.ss+dy[i];
			
			if(x>n or x < 1 or y < 1 or y > m) continue;
			if(vis[x][y]) continue;
			if(maze[x][y]=='#') continue;
			
			if(maze[x][y]=='.')
			{
				cnt++;
				vis[x][y] = true;
				q.push({x,y});
				v.push_back({x,y});
			} 
		}
	}
	if(cnt<d)
	{
		for(auto x : v)
			maze[x.ff][x.ss] = '#';
	}
}

void solve()
{
	cin >> n >> m >> d;
	
	rep(i,0,n+1)
		rep(j,0,m+1)
			maze[i][j] = '.';
			
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> maze[i][j];
	bfs();
	
	rep(i,1,n)
		rep(j,1,m)
			if(!vis[i][j] and maze[i][j]=='.')
				Bfs(i, j);
	
	rep(i,1,n)
	{
		rep(j,1,m) cout << maze[i][j];
		cout << endl;
	}
}

int main()
{
	solve();
	return 0;
}