Игра
Игра <Хамелеон> происходит в
квадрате 3 × 3, в клетках которого находятся 8 фишек с буквами этого
слова, а одна из клеток пуста. За один ход разрешается одну из фишек
переместить на соседнюю пустую клетку. Цель игры - достигнуть расположения
фишек, указанного на рисунке.
Напишите программу, которая
определяет план достижения цели за минимально возможное число ходов, либо
сообщает, что цели достичь нельзя.
Входные данные:
матрица 3 × 3, составленная из больших букв русского алфавита (в
кодировке DOS).
Выходные данные: ваша
программа должна вывести искомое число ходов. Если плана не существует,
выведите сообщение <NO>.
Пример входных данных:
ХАМ
Е Е
ОЛН
Пример выходных данных:
2
