Задача AB-шки
Дана последовательность из 2N ячеек. Две соседние из них - пустые, а
остальные содержат N-1 символов A и N-1 символов B.
Пример для N = 5:
A B B A A B A B
Правила перемещения:
Содержимое любых двух соседних непустых ячеек можно, сохраняя их порядок,
пересылать в пустые ячейки.
Цель:
Используя правило перемещения, достичь конфигурации, в которой все символы A расположены левее всех символов B. Местоположение пустых ячеек после перемещений не имеет значения.
Задание:
Написать программу, которая:
- Вводит с клавиатуры начальную конфигурацию в виде последовательности символов A, B и нулей для пустых ячеек, а также моделирует перемещения.
- Для заданной начальной конфигурации определяет по крайней мере один план перемещений, с помощью которого можно достичь цели, или сообщает, что такого плана не существует. Вывод должен содержать начальную конфигурацию, промежуточные конфигурации после каждого шага, а также заключительную конфигурацию.
- Находит план достижения цели за минимальное число шагов.
Результаты:
Представить по крайней мере хотя бы одно решение для примера, приведенного
выше.
