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`: Извлекаем текущую позицию из очереди.

9. `if (x, y) in goals: …`: Если текущая позиция является целью, возвращаем расстояние и координаты.

10. `for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: …`: Перебираем все возможные направления движения (вверх, вниз, влево, вправо).

11. `nx, ny = x + dx, y + dy`: Вычисляем новые координаты.

12. `if is_valid(nx, ny) and (nx, ny) not in visited: …`: Если новые координаты валидны и не были посещены, добавляем их в очередь и множество посещённых, обновляем расстояние.

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

Основной цикл для моделирования ходов

```python

for _ in range(K):

```

1. `for _ in range(K):`: Запускаем цикл для моделирования каждого хода.

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

```python

_, 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)

1. `_, nearest_sheep = bfs(pastukh, sheep_positions)`: Ищем ближайшую овцу для пастуха.

2. `if nearest_sheep: …`: Если найдена овца, определяем направление движения пастуха.

3. `px, py = pastukh`: Текущие координаты пастуха.

4. `sx, sy = nearest_sheep`: Координаты ближайшей овцы.

5. `if px < sx: px += 1 …`: Если пастух находится левее овцы, он движется вправо. Аналогично для других направлений.

6. `pastukh = (px, py)`: Обновляем координаты пастуха.

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

```python

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

1. `new_wolf_positions = []`: Создаем список для обновленных позиций волков.

2. `for wx, wy in wolf_positions: …`: Перебираем текущие позиции всех волков.

3. `_, target = bfs((wx, wy), sheep_positions + [pastukh])`: Ищем ближайшую цель (овца или пастух) для волка.

4. `if target: …`: Если найдена цель, определяем направление движения волка.

5. `tx, ty = target`: Координаты ближайшей цели.

6. `if wx < tx: wx += 1 …`: Если волк находится левее цели, он движется вправо. Аналогично для других направлений.

7. `new_wolf_positions.append((wx, wy))`: Добавляем обновленные координаты волка в список.

8. `wolf_positions = new_wolf_positions`: Обновляем позиции волков.

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

```python

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