Условие:

Пастух охраняет стадо овец на лугу. На лугу также находятся волки. Луг можно представить в виде сетки (N \times M) клеток. Каждая клетка может быть либо пустой, либо содержать овцу, либо волка, либо пастуха.

Пастух может двигаться на одну клетку вверх, вниз, влево или вправо (но не по диагонали). Волки также могут двигаться на одну клетку в любом из четырех направлений. В каждом ходу все волки и пастух делают один шаг одновременно. Если волк попадает на клетку с овцой, он съедает овцу. Если волк попадает на клетку с пастухом, волк останавливается, и пастух побеждает в этом раунде.

Ваша задача – написать программу, которая моделирует передвижения пастуха и волков на лугу, чтобы пастух мог спасти как можно больше овец.

Входные данные:

– Размер луга (N \times M)

– Позиции овец, волков и пастуха на лугу

– Количество ходов, которые нужно смоделировать

Выходные данные:

– Позиции всех овец, волков и пастуха после заданного количества ходов

– Количество спасённых овец

Пример входных данных:

5 5

Пастух: 2 2

Овцы: 1 1, 3 3, 4 4

Волки: 0 0, 4 0

Ходы: 5

Пример выхода:

Пастух: 3 3

Овцы: 1 1, 3 3

Волки: 0 1, 4 1

Спасённые овцы: 2

Пояснение:

1. На вход подаются размеры луга (5x5), стартовые позиции пастуха (2,2), овец (1,1), (3,3), (4,4), волков (0,0), (4,0) и количество ходов (5).

2. Программа моделирует передвижение пастуха и волков в течение 5 ходов и выводит финальные позиции и количество спасённых овец.

Примечания:

– Считайте, что пастух и волки могут двигаться на одну клетку в одном направлении за один ход.

– Волки преследуют овец или пастуха, выбирая направление, которое минимизирует расстояние до ближайшей овцы или пастуха.

– Овцы остаются на месте.

– Если несколько волков попадают на одну клетку одновременно, один волк съедает овцу, остальные остаются на этой клетке.

Идея решения задачи о пастухе и волках

1. Представление поля

Представим луг в виде двумерного массива (списка списков). Каждая клетка может содержать одну из следующих сущностей:

– Пустая клетка (`.`)

– Пастух (`P`)

– Овца (`S`)

– Волк (`W`)

2. Чтение и обработка входных данных

Читаем размеры луга, позиции пастуха, овец и волков, а также количество ходов. Инициализируем двумерный массив для представления луга и заполняем его исходными данными.

3. Логика движения

– Пастух движется в направлении ближайшей овцы, чтобы защитить её.

– Можно использовать алгоритм поиска кратчайшего пути, например, алгоритм A* или простейший жадный алгоритм, чтобы определить направление движения пастуха к ближайшей овце.

– Волки движутся в направлении ближайшей овцы или пастуха.

– Для каждого волка определяем кратчайший путь до ближайшей цели и движемся в этом направлении.

– На каждом шагу все волки и пастух совершают по одному движению одновременно. Важно учесть, что сначала нужно рассчитать новые позиции всех сущностей, а затем обновить поле.

4. Обработка столкновений

– Если волк попадает на клетку с овцой, овца съедается.

– Если волк попадает на клетку с пастухом, волк останавливается и считается побеждённым, и пастух побеждает в этом раунде.

5. Моделирование ходов

– Повторяем процесс движения и обновления поля для заданного количества ходов.

– Отслеживаем количество спасённых овец.

6. Вывод результатов

– По завершении всех ходов выводим конечные позиции пастуха, овец и волков.

– Выводим количество спасённых овец.

Пример реализации на Python

```python

from collections import deque

# Чтение входных данных

N, M = map(int, input().split())

pastukh = tuple(map(int, input().split()))

sheep_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]

wolf_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]

K = int(input())

# Инициализация поля

field = [['.' for _ in range(M)] for _ in range(N)]

field[pastukh[0]][pastukh[1]] = 'P'

for x, y in sheep_positions:

field[x][y] = 'S'

for x, y in wolf_positions:

field[x][y] = 'W'

# Вспомогательные функции

def is_valid(x, y):

return 0 <= x < N and 0 <= y < M

def bfs(start, goals):

queue = deque([start])

visited = set()

visited.add(start)

dist = {start: 0}

while queue:

x, y = queue.popleft()

if (x, y) in goals:

return dist[(x, y)], (x, y)

for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:

nx, ny = x + dx, y + dy

if is_valid(nx, ny) and (nx, ny) not in visited:

queue.append((nx, ny))

visited.add((nx, ny))

dist[(nx, ny)] = dist[(x, y)] + 1

return float('inf'), None

# Основная логика движения и моделирования

for _ in range(K):

# Движение пастуха

_, nearest_sheep = bfs(pastukh, sheep_positions)

if nearest_sheep:

px, py = pastukh

sx, sy = nearest_sheep

if px < sx: px += 1

elif px > sx: px -= 1

elif py < sy: py += 1

elif py > sy: py -= 1

pastukh = (px, py)

# Движение волков

new_wolf_positions = []

for wx, wy in wolf_positions:

_, target = bfs((wx, wy), sheep_positions + [pastukh])

if target:

tx, ty = target

if wx < tx: wx += 1

elif wx > tx: wx -= 1

elif wy < ty: wy += 1

elif wy > ty: wy -= 1

new_wolf_positions.append((wx, wy))

wolf_positions = new_wolf_positions

# Обновление поля и проверка столкновений

field = [['.' for _ in range(M)] for _ in range(N)]

field[pastukh[0]][pastukh[1]] = 'P'

new_sheep_positions = []

for x, y in sheep_positions:

if (x, y) not in wolf_positions:

field[x][y] = 'S'

new_sheep_positions.append((x, y))

sheep_positions = new_sheep_positions

for x, y in wolf_positions:

if field[x][y] == 'P':

field[x][y] = 'P'

else:

field[x][y] = 'W'

# Вывод результатов

print(f"Пастух: {pastukh[0]} {pastukh[1]}")

print("Овцы:", ', '.join(f"{x} {y}" for x, y in sheep_positions))

print("Волки:", ', '.join(f"{x} {y}" for x, y in wolf_positions))

print(f"Спасённые овцы: {len(sheep_positions)}")

```

Давайте разберем код более подробно на каждом этапе.

Чтение входных данных

```python

N, M = map(int, input().split())

pastukh = tuple(map(int, input().split()))

sheep_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]

wolf_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]

K = int(input())

```

1. `N, M = map(int, input().split())`: Считываем размеры луга (количество строк и столбцов).

2. `pastukh = tuple(map(int, input().split()))`: Считываем координаты пастуха и сохраняем их как кортеж.

3. `sheep_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]`: Считываем позиции всех овец. Каждая позиция считывается как кортеж координат, и все позиции сохраняются в список.

4. `wolf_positions = [tuple(map(int, pos.split())) for pos in input().split(',')]`: Считываем позиции всех волков аналогично овцам.

5. `K = int(input())`: Считываем количество ходов.

Инициализация поля

```python

field = [['.' for _ in range(M)] for _ in range(N)]

field[pastukh[0]][pastukh[1]] = 'P'

for x, y in sheep_positions: