Трое миссионеров и трое людоедов стоят на одном берегу реки. Им нужно перебраться на другой берег, а из транспорта — только одна лодка.
Есть опасное условие: на любом берегу, если там остаются миссионеры, людоедов не должно быть больше, иначе миссионеров съедят.
Лодка рассчитана максимум на двух человек.
Правила:
- лодка перевозит максимум двоих;
- лодка не может плыть пустой — в ней всегда должен быть хотя бы один человек;
- на каждом берегу, где есть миссионеры, людоедов не может оказаться больше.
Вопрос
Как всем шестерым переправиться на другой берег?
Краткая справка
Это классическая задача про переправу и ограничение «нельзя оставлять миссионеров в меньшинстве». Обычно решается последовательностью ходов туда-обратно.
Формат ответа (переправы)
Пишите рейсы подряд. В каждом рейсе укажите пассажиров лодки: LL, MM, LM, L0 или M0.
Разделять можно чем угодно (пробелы, запятые, |, переносы строк) — учитываем только символы M, L и 0.
0 означает «едет один»: L0 = один людоед, M0 = один миссионер. Пустая лодка запрещена.
Шаблон (11 групп):
xx xx xx xx xx xx xx xx xx xx xx
Пример записи (не решение):
LL | L0 | MM | M0 | LM | L0
Извините за такой формат: иначе переправу трудно проверить автоматически.
Решение
Решение (11 рейсов — минимум):
LL L0 LL L0 MM LM MM L0 LL L0 LL
11 — минимум (доказуемо). Вариантов переправ много.