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

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

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

Пастбище можно представить как прямоугольник из 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";
}