Введение - sergeresko/Lem_in-explanation GitHub Wiki
Напомню, что нужно найти такое решение, которое, будучи записанным в формате, указанном в задании, будет состоять из как можно меньшего числа строк.
Вполне возможно, что для одной и той же конфигурации муравейника существует несколько решений, которые удовлетворяют этому условию минимальности. Мы можем в качестве ответа выбрать любое из них.
Моя идея состоит в том, что для любого муравейника среди всех оптимальных решений существует решение определённого вида, а именно такое, в котором используется несколько непересекающихся путей из start в end, по каждому из которых параллельно движется непрерывная группка муравьёв, причём все группки достигают end как можно более одновременно. Решение этого вида мы будем искать.
Возникает два вопроса:
- Сколько путей использовать и какие именно?
- Сколько муравьёв отправлять по каждому из этих путей?
Ответить на первый вопрос помогает алгоритм Бхандари. Его я опишу позже. Ответ на второй вопрос я нашёл сам. Он описан на следующей странице.