Некоторое время назад в задаче были изменены тесты (и немного условие), поэтому решение из предыдущего разбора не проходит: Задача 707. Zuma. Давайте перерешивать: Если представить, что состояние на поле - это вершина графа, а выстрелы, которые ведут в другие состояния - это рёбра в графе, тогда получается, что надо найти кратчайший путь в графе из текущей вершины в вершину с пустым состоянием. Эта задача решается с помощью обхода в ширину (bfs). Но всевозможных состояний может быть очень много, поэтому надо попробовать их уменьшить (при этом не пропустив кратчайший путь)...

Давно не было решений на С++. Сегодня разберём непростую задачу на динамическое программирование по подмножествам, которую на Python затолкать в ограничения очень сложно. Читаем условие: Почти всегда, когда в задаче есть перебор перестановок, можно решение за O(N!) заменить решением за O(N * 2^N), используя динамическое программирование по подмножествам. Это всё ещё экспоненциальное решение, но константа сильно меньше. В нашем случае, если решать задачу в лоб, то надо каждую перестановку ещё проверять на удовлетворение условий К-перестановки...