eolymp
bolt
Try our new interface for solving problems
Məsələlər

Пирожок Дракона

Пирожок Дракона

Zaman məhdudiyyəti 60 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Пирожок Дракона - это головоломка со скольжением на торе. Поверхность тора разбита на девять квадратов как показано на Рисунке 1. Два квадрата с общей стороной обозначены одной буквой. На Рисунке 2 отображены пары квадратов, являющиеся соседними. Фишки пронумерованы числами от 1 до 8 и размещены на восьми из девяти квадратах, последний квадрат остается пустым.

Рисунок 1. 3×3 Тор Пирожка Дракона

Фишка может перемещаться (скользить) в пустую ячейку из одной из соседних ячеек. Задача головоломки - путем перемещений фишек получить из начальной комбинации заданную. На Рисунке 3 приведен пример перемещений фишек из одного состояния в результате четырех возможных ходов. Стоимость перемещения фишки зависит от направления, но не от ее местоположения.

Ваша задача - найти наименьшую стоимость перемещения фишек из начального состояния в конечное.

Рисунок 2. Соседы

Рисунок 3. Примеры операций скольжения

В отличии от задачи на плоскости, на торе любое конечное состояние фишек может быть получено из любого начального состояния.

Giriş verilənləri

Состоит из не более чем 30 тестов.

Каждый тест состоит из семи строк. Первая строка содержит два натуральных числа c_h и c_v - стоимость передвижения фишки в горизонтальном и вертикальном направлении. Оба значения c_h и c_v меньше 100. Следующие три строки задают начальное расположение, а последние три строки - финальное в следующем формате:

d_A d_B d_C

d_D d_E d_F

d_G d_H d_I

Каждая строка содержит три цифры, разделенных пробелом. Цифра d_X (X одна из букв от A до I) указывает на состояние квадрата X как показано на Рисунке 2. Цифры 1, ..., 8 указывают на номер фишки в квадрате. Цифра 0 означает, что квадрат пустой.

Последняя строка содержит два нуля и не обрабатывается.

Çıxış verilənləri

Для каждого теста вывести в отдельной строке наименьшую стоимость, за которую можно получить конечное состояние. Общая стоимость равна сумме стоимостей ходов всех фишек из начального состояния в конечное.

Nümunə

Giriş verilənləri #1
4 9
6 3 0
8 1 2
4 5 7
6 3 0
8 1 2
4 5 7
31 31
4 3 6
0 1 5
8 2 7
0 3 6
4 1 5
8 2 7
92 4
1 5 3
4 0 7
8 2 6
1 5 0
4 7 3
8 2 6
12 28
3 4 5
0 2 6
7 1 8
5 7 1
8 6 2
0 3 4
0 0
Çıxış verilənləri #1
0
31
96
312
Mənbə 2013 ACM International Collegiate Programming Contest, Asia Regional Contest, Aizu, Ноябрь 24, Задача Е