40 задач на Python. Джеймс Девис

аг одновременно. Если волк попадает на клетку с овцой, он съедает овцу. Если волк попадает на клетку с пастухом, волк останавливается, и пастух побеждает в этом раунде.

      Ваша задача – написать программу, которая моделирует передвижения пастуха и волков на лугу, чтобы пастух мог спасти как можно больше овец.

      Входные данные:

      – Размер луга (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