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

Условие:

Пастух охраняет стадо овец на лугу. На лугу также находятся волки. Луг можно представить в виде сетки (N \times M) клеток. Каждая клетка может быть либо пустой, либо содержать овцу, либо волка, либо пастуха.

Пастух может двигаться на одну клетку вверх, вниз, влево или вправо (но не по диагонали). Волки также могут двигаться на одну клетку в любом из четырех направлений. В каждом ходу все волки и пастух делают один шаг одновременно. Если волк попадает на клетку с овцой, он съедает овцу. Если волк попадает на клетку с пастухом, волк останавливается, и пастух побеждает в этом раунде.

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

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

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

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: …`: Если новые координаты валидны и не были посещены, добавляем их в очередь и множество посещённых, обновляем расстояние.

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

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