Ваша задача – написать программу, которая моделирует передвижения пастуха и волков на лугу, чтобы пастух мог спасти как можно больше овец.
Входные данные:
– Размер луга (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