|
Название задачи: Хамелеон . |
 |
Условие
Игра «Хамелеон» происходит в квадрате 3 × 3, в клетках которого находятся 8 фишек с буквами этого слова, а одна из клеток пуста. За один ход разрешается одну из фишек переместить на соседнюю пустую клетку. Цель игры – достигнуть расположения фишек, указанного на рисунке.| Х | А | М |
| Е | Л | Е |
| О | Н |
Напишите программу, которая определяет план достижения цели за
минимально возможное число ходов, либо сообщает, что цели достичь нельзя.
Входные данные
Во входном файле находится матрица
3 × 3, составленная из больших букв русского алфавита.
Выходные данные
Ваша программа должна вывести в первую строку выходного файла искомое
число ходов, а в последующие – их список. Каждый ход задается
координатами той фишки, которая перемещается. Если плана не существует,
выведите в выходной файл сообщение «Нет решения».
Пример входного файла
ХАМ
Е Е
ОЛН
Пример выходного файла
2
3 2
3 3
Решение
Скачать архив тестов и решенийПостроим граф, вершины которого будут соответствовать возможным конфигурациям игры, а ребра – разрешенным правилами переходам между ними. (Мы получим граф с 9! / 2 = 181440 вершинами, каждой из которых инцидентно от 2 до 4 ребер.) Тогда наша исходная задача о поиске кратчайшей последовательности ходов сведется к задаче о нахождении кратчайшего пути в графе от заданной вершины до вершины, соответствующей конфигурации с рисунка. Для решения последней используем алгоритм поиска в ширину.
В данной задаче искомый путь всегда будет существовать. Действительно, несложно показать, что мы можем получить любую перестановку исходных букв (если читать квадрат 3 × 3 слева направо и сверху вниз) той же четности, что и исходная. Но за счет того, что у нас имеются две одинаковые буквы Е, требуемое расположение фишек всегда достижимо.
Для нахождения всех вершин кратчайшего пути необходимо при поиске в ширину для каждой посещенной вершины v запоминать ту вершину, из которой мы пришли в v. Необязательно хранить ее номер, достаточно хранить, в каком из четырех направлений перемещалась пустая клетка.
Другая проблема, с которой мы сталкиваемся в этой задаче, состоит в
нумерации конфигураций числами. Алгоритмы такого типа обсуждаются в
главе 5. Кроме того, при реализации решения в некоторых системах
программирования, ограничивающих размер сегментов стека и данных 64
килобайтами (такой средой является, например, Turbo
Pascal), возникает необходимость либо работать с динамической памятью, либо использовать для
хранения структур данных как сегмент данных, так и сегмент стека, и при этом
еще и использовать битовые вычисления.
Упражнение
Какое минимальное количество бит необходимо для хранения информации о
каждой вершине построенного графа?
Замечания
Игра, описанная в задаче, взята из книги [Калужнин 85]. В [Лапунов 93, п. 2.2]
рассматривается аналогичная задача без требования минимизации числа ходов,
там же приведен листинг программы для этого варианта задачи. Сравните также
задачу «Хамелеон» с задачами «AB» и «Игра 14» первых международных
олимпиад [Кирюхин 96].
