Решение задачи Лабиринт с Codeforces

Без пояснения   Просмотров: 161

Павел обожает клетчатые лабиринты. Клетчатый лабиринт — это прямоугольный лабиринт размера n × m, где каждая клетка либо свободна, либо является стеной, а перемещаться из одной клетки в другую можно только в том случае, если они обе свободные и имеют общую сторону.

Павел нарисовал клетчатый лабиринт, все свободные клетки которого образуют связную область, то есть из любой свободной клетки можно добраться до любой другой. Павлу не нравится, что в его лабиринте слишком мало стен. Он хочет превратить ровно k свободных клеток в стены таким образом, чтобы все оставшиеся свободные клетки по прежнему образовывали бы связную область. Помогите ему.

Код 

#include<bits/stdc++.h>
using namespace std;

int n,m,k;
string s[1000],t;
bool b[1000][1000];

void dfs(int x,int y)
{
	b[x][y]=1;
	for(int i=-1;i<2;i++)
	{
		if(s[i+x][y]=='.'&&!b[i+x][y])
			dfs(i+x,y);
	}
	for(int j=-1;j<2;j++)
	{
		if(s[x][j+y]=='.'&&!b[x][j+y])
			dfs(x,j+y);
	}
	if(k>0)
	{
		k--;
		s[x][y]='X';
	}
	return;
}

int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		s[i]=" ";
		cin>>t;
		s[i]+=t;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			if(s[i][j]=='.'&&!b[i][j])
				dfs(i,j);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cout<<s[i][j];
		cout<<endl;
	}
	return 0;
}

         

Администратор Photo Автор: Администратор




Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться


© 2020 mycod   [email protected]  Карта сайта   Правообладателям