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:
field[x][y] = 'S'
for x, y in wolf_positions:
field[x][y] = 'W'
1. `field = [['.' for _ in range(M)] for _ in range(N)]`: Создаем двумерный массив, представляющий луг, заполняя его пустыми клетками (`.`).
2. `field[pastukh[0]][pastukh[1]] = 'P'`: Размещаем пастуха на лугу в начальной позиции.
3. `for x, y in sheep_positions: field[x][y] = 'S'`: Размещаем овец на их начальных позициях.
4. `for x, y in wolf_positions: field[x][y] = 'W'`: Размещаем волков на их начальных позициях.
Вспомогательные функции
Проверка валидности координат
```python
def is_valid(x, y):
return 0 <= x < N and 0 <= y < M
```
1. `def is_valid(x, y): return 0 <= x < N and 0 <= y < M`: Функция проверяет, находятся ли координаты в пределах луга. Если координаты выходят за границы, возвращается False, иначе True.
Поиск кратчайшего пути (BFS)
```python
from collections import deque
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
```
1. `from collections import deque`: Импортируем deque для реализации очереди.
2. `def bfs(start, goals):`: Определяем функцию для поиска кратчайшего пути от `start` до ближайшей цели из `goals`.
3. `queue = deque([start])`: Инициализируем очередь с начальной позицией.
4. `visited = set()`: Создаем множество для отслеживания посещённых клеток.
5. `visited.add(start)`: Добавляем начальную позицию в множество посещённых.
6. `dist = {start: 0}`: Инициализируем словарь для хранения расстояний от начальной точки.
7. `while queue: …`: Запускаем цикл, пока есть элементы в очереди.
8. `x, y = queue.popleft()`: Извлекаем текущую позицию из очереди.