Глава 1: Задачи на логику и сообразительность
1. Задача о пастухе и волках
Условие:
Пастух охраняет стадо овец на лугу. На лугу также находятся волки. Луг можно представить в виде сетки (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. Чтение и обработка входных данных
Читаем размеры луга, позиции пастуха, овец и волков, а также количество ходов. Инициализируем двумерный массив для представления луга и заполняем его исходными данными.
