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:
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:
