Читать книгу 40 задач на Python онлайн

– Овца (`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: