Представьте задачу как последовательность состояний
Состояние — это полный список того, кто находится слева, кто справа и где расположен транспорт. После каждого рейса проверяйте запреты. Если коза осталась с капустой без человека, такое состояние недопустимо и ветку можно отбросить.
Короткая запись вроде «лево: волк, капуста; право: коза + лодка» надёжнее памяти. Она также показывает, когда кого-то приходится возвращать, хотя на первый взгляд это кажется движением назад.
Ищите ключевого пассажира
В классической задаче с волком, козой и капустой именно коза конфликтует с обоими соседями. Поэтому её приходится использовать как подвижный элемент: перевезти, вернуть и снова перевезти. Определение такого участника часто сразу задаёт каркас маршрута.
В задачах про мост ключевыми становятся самые быстрые участники: они дешевле возвращают фонарь. Но иногда выгодно отправить двух медленных вместе, чтобы не платить их время дважды.
Как доказать, что ходов меньше быть не может
Недостаточно найти работающий маршрут, если спрашивают минимум. Посчитайте обязательные события: каждый предмет должен хотя бы раз попасть на другой берег, транспорт после промежуточных рейсов должен возвращаться, а запрещённые пары требуют дополнительных перемещений.
Сравните найденный маршрут с этой нижней границей. Если маршрут использует ровно столько неизбежных действий, он минимален. Для больших задач удобно построить граф допустимых состояний и искать кратчайший путь.
Коротко о частом
Вопросы и ответы
Почему иногда нужно везти предмет обратно?
Возврат меняет запрещённое сочетание на берегу и доставляет лодку или фонарь для следующего рейса. Без него допустимый маршрут может быть невозможен.
Как решать задачу с большим числом участников?
Кодируйте состояние списком или битовой маской, перечисляйте допустимые переходы и ищите кратчайшую последовательность без повторения состояний.