<ПРЕД Задача:
СЛЕД>
Задачу решили 272 пользователя: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Головоломка "Восьминашки"

Time limit = 2 секунд(ы)

Memory limit = 10Mb

Дано квадратное поле размера 3x3 и в нем расположены 8 квадратных фишек 1x1. Один квадрат поля не покрыт.

На фишках написаны цифры от 1 до 8. За один ход разрешено оду из фишек, соседних со свободным квадратом, переместить на этот свободный квадрат.

Задача --- из данной позиции получить конечную позицию за минимальное число ходов.


1 2 3
4 5 6
7 8  

Рис. 1. Конечная позиция.

a1 a2 a3
a4 a5 a6
a7 a8 a9

Рис. 2. Порядок ячеек в входных данных.

Вход. Вход состоит из одной строчки, в которой дано описание позиции фишек, а именно указаны идентификаторы a1 a2 a3 ... a9 в порядке? указанном на рисунке 2.

Выход. Выведите в первй строчке Yes или No в зависимости от того, можно получить конечную позицию или нет. Если Yes, то выведите минимальное число ходов, которое нужно сделать, чтобы её получить.

Вход#1
1 2 3 4 5 6 7 8 0
Выход#1
Yes
0
Вход#2
0 1 2 3 4 5 6 7 8 
Выход#2
Yes
22

Автор:
Фольклор. Тесты и описание подготовил Челноков Владимир.
5 марта 2006

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 170ms

SW soft NIX
ID = 75.101.220.230