Решение задачи Защитить овец с Codeforces

С пояснением   Просмотров: 164

Боб — пастух. Он пасет своих овец на большом пастбище. Недавно волки утащили нескольких из его овец. Поэтому он решил обзавестись несколькими собаками-пастухами, которые будут защищать всех его овец.

Пастбище можно представить как прямоугольник из R × C клеток. Каждая клетка либо пустая, либо содержит овцу, волка или собаку. Овцы и собаки не могут двигаться, однако волки могут перемещаться по пастбищу свободно, каждый раз перемещаясь влево, вправо, вверх или вниз в соседнюю клетку. Если волк доберется до клетки с овцой, он съест ее. Однако волк не может зайти в клетку, где находится собака.

Изначально собак нет. Расположите собак на пастбище так, чтобы никакой волк не мог бы добраться до никакой овцы, или определите, что это невозможно. Обратите внимание на то, что у вас достаточно собак, поэтому вам не нужно минимизировать их количество.

Код 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m;
string s[600];
ll f(ll i,ll j)
{
	if(i<0||j<0||i==n||j==m)
		return 0;
	if(s[i][j]=='S')
		return 1;
	return 0;
}
int main() {
	ll i=0,j;
	cin>>n>>m;
	while(i<n)
	cin>>s[i++];
	i=0;
	while(i<n)
	{
		j=0;
		while(j<m)
		{
			if(s[i][j]=='.')
				s[i][j]='D';
			else if(s[i][j]=='W')
			if(f(i+1,j)+f(i-1,j)+f(i,j+1)+f(i,j-1))
			{
				cout<<"No";
				return 0;
			}
			j++;
		}
		i++;
	}
	i=0;
	cout<<"Yes\n";
	while(i<n)
	cout<<s[i++]<<"\n";
}

         

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


Пояснение к задаче

Предположим, что в каких-то соседних клетках сидят овца и волк. Тогда очевидно, что в этом случае ответ "NO" — конкретно этот волк всегда сможет атаковать эту овцу.

Если же ни одна овца не соседствует с волком, то ответ "YES". Самый простой метод обеспечить защиту всех овец — поставить в каждую пустую клетку по собаке. Тогда ни один волк не сможет двигаться и все овцы находятся в безопасности.



Комментарии

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


© 2020 HSECODES [email protected] Карта сайта