Чтение онлайн

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:

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