eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Игра

Игра

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Наверняка всем знакома детская игра «пятнашки». В этой задаче мы рассмотрим более простую игру - «восмернашки». Игровое поле в этой игре представляет собой квадрат размером 3х3 клетки. Имеется 8 квадратных фишек, пронумерованных цифрами от 1 до 8. Эти фишки в произвольном порядке расставлены в клетках поля. Одна клетка остается свободной. За один ход можно переместить на свободную клетку поля любую из соседних фишек, то есть фишку, стоящую справа или слева, или сверху или снизу от свободной клетки. Цель игры — перемещая фишки по игровому полю описанным выше способом, расставить все фишки в правильном порядке:

123

456

780

цифрой 0 обозначена свободная клетка. Вам необходимо для заданного начального положения фишек определить минимальное количество ходов, за которое можно расставить фишки в правильном порядке.

Входные данные

Входной файл содержит начальную позицию в игре. Позиция задается тремя строками, в каждой из который записаны три цифры без пробелов. Для задания позиции используются цифры от 0 до 8. Каждая цифра встречается ровно один раз.

Выходные данные

Единственная строка выходного файла должна содержать минимальное количество ходов, за которое можно расставить фишки в правильном порядке. Если входные данные таковы, что фишки расставить нельзя, необходимо вывести -1 (минус один). Вывод должен заканчиваться переводом строки.

Пример

Входные данные #1
826
704
153
Выходные данные #1
-1
Источник Крым 2010