UPD: Тест и условие задачи были изменены, поэтому описанное ниже решение уже не подходит. Смотрите новую версию разбора: Задача 707. Zuma.
На сайте acmp.ru добавились 300 новых задач, и сейчас самое время их решить.
Если представить, что состояние на поле - это вершина графа, а выстрелы, которые ведут в другие состояния - это рёбра в графе, тогда получается, что надо найти кратчайший путь в графе из текущей вершины в вершину с пустым состоянием. Эта задача решается с помощью обхода в ширину (bfs), и при таких небольших ограничениях можно писать на Python.
Напишем функцию fold, которая будет реализовывать цепочку исчезновений групп из 3 и более шаров. Здесь примечательным является применение барьерного метода: чтобы отдельно не рассматривать исчезновение крайней справа группы, дописываем в конец отличный от всех символ - он ни с чем никогда не образует группу и не исчезнет, и не повлияет на результат, но теперь крайняя группа перестала быть такой, и может рассматриваться на общих основаниях. А в конце не забываем вернуть всё, кроме последнего символа.
Заметим, что все выстрелы в одну группу одноцветных шаров приводят к одному результату, а поэтому, чтобы уменьшить количество операций, будем рассматривать только выстрелы в конец группы (это согласуется с условием, что среди всех подходящих надо выбрать самый правый).
В остальном код представляет собой стандартный bfs, только в словарь складываем всю полезную информацию, чтобы потом легко можно было восстановить последовательность выстрелов без лишних вычислений.
В этой задаче довольно трудно оценить количество состояний и переходов между ними, но интуитивно кажется, что при условии достижения пустого состояния за 10 выстрелов изначально должно быть большое количество шаров одного цвета, а значит существенное уменьшение количества переходов и различных промежуточных состояний.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.