Некоторое время назад в задаче были изменены тесты (и немного условие), поэтому решение из предыдущего разбора не проходит: Задача 707. Zuma. Давайте перерешивать:
Если представить, что состояние на поле - это вершина графа, а выстрелы, которые ведут в другие состояния - это рёбра в графе, тогда получается, что надо найти кратчайший путь в графе из текущей вершины в вершину с пустым состоянием. Эта задача решается с помощью обхода в ширину (bfs).
Но всевозможных состояний может быть очень много, поэтому надо попробовать их уменьшить (при этом не пропустив кратчайший путь). Во-первых, понятно, что стрелять всегда можно в начало группы. Это уменьшит количество рёбер, но не состояний.
Во-вторых, стрелять надо всегда до исчезновения группы. То есть, если это группа из одного шара, то надо сразу делать два выстрела слева от него. Эта оптимизация сильно уменьшает и количество состояний, и количество рёбер. Например для даже для небольшого теста ABC:
- с оптимизацией: ABC, BC, AC, AB, A, B, C - 7 состояний
- без оптимизации: ABC, AABC, ABBC, ABCC, BC, AABBC, AABCC, AC, ABBCC, AB, BBC, BCC, AACC, AABBCC, AAB, AAC, ACC, ABB, C, BBCC, B, CC, AA, AACC, AABB, A, BB - 27 состояний
Но тогда у нас возникают шаги длины 2, а классический поиск в ширину такого не поддерживает, так как будет нарушаться инвариант, что в очереди состояния идут по увеличению расстояния от начальной точки. На такой случай есть, так называемая, модификация 1-2 bfs. Его и напишем.
Сначала считаем входные данные. А также, преобразуем строку в список пар: буква и количество. Такое хранение сильно облегчит обработку выстрелов (как в написании кода, так и во времени работы):
Как и в предыдущем решении, напишем функцию fold, которая будет схлопывать две части ряда после выстрела (и уничтожения одной группы). Логика функции очень простая: на вход придит две части ряда, и мы двумя указателя синхронно движемся в разные стороны пока выполняются условия схлопывания. После этого склеиваем новый ряд:
Для реализации 1-2 bfs нам понадобится 3 очереди (а не одна):
- по которой мы идём сейчас
- очередь состояний, расстояние до которых на 1 больше, чем до текущего
- очередь состояний, расстояние до которых на 2 больше, чем до текущего
А ещё нам понадобится словарь состояний, в который будем заносить историю переходов, чтобы потом можно было восстановить маршрут:
Основной цикл в модифицированном поиске в ширину ничем не отличается от обычного: бежит до тех пор, пока не придём в пустое состояние, и каждый раз берём следующий элемент из текущей очереди:
Для каждого состояния мы должны проверить все варианты выстрелов, то есть для каждого элемента в списке попробовать добить его до 3 или больше:
Именно здесь и происходит основное отличие от обычного поиска в ширину. Мы смотрим, сколько шаров надо было выстрелить, чтобы получилось схлопывание текущей группы, и заносим результат в соответствующую очередь - вторую или третью, и в словарь с историей тоже сохраняем один или два выстрела.
И второе отличие - это переключение очередей, когда текущая заканчивается:
После выполнения основного цикла, нам надо восстановить ответ. Как это обычно бывает в динамическом программировании (а поиск в ширину - в чистом виде динамическое программирование), восстановление ответа происходит в обратном порядке - от конечной точки к исходной:
Такое решение просто залетает на Python. Но здесь важно понять принцип работы 1-2 bfs, а также то, что его можно модифицировать и на большее число очередей.
Предыдущий выпуск: Задача 29. Компьютерная игра
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.