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

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:

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