Пиріжок Дракона#6782
Пиріжок Дракона — це головоломка з ковзанням на торі. Поверхня тора розділена на дев'ять квадратів, як показано на Рисунку 1. Два квадрати, що мають спільну сторону, позначені однією літерою. На Рисунку 2 зображені пари квадратів, які є сусідніми. Плитки (кубики) пронумеровані числами від до і розміщені на восьми з дев'яти квадратів, залишаючи один квадрат порожнім.
Рисунок 1. 3 \times 3 Тор Пиріжка Дракона
Плитка може переміщатися (ковзати) в порожню клітинку з однієї із сусідніх клітинок. Завдання головоломки — шляхом переміщень плиток отримати з початкової комбінації задану. На Рисунку 3 наведено приклад переміщень плиток з одного стану в результаті чотирьох можливих ходів. Вартість переміщення плитки залежить від напрямку, але не від її місцезнаходження.
Ваше завдання — знайти найменшу вартість переміщення плиток з початкового стану в кінцевий.
Рисунок 2. Сусіди
Рисунок 3. Приклади операцій ковзання
На відміну від задачі на площині, на торі з будь-якого початкового стану можна отримати будь-який кінцевий стан плиток.
Складається з не більше ніж тестів.
Кожен тест складається із семи рядків. Перший рядок містить два натуральних числа c_h і c_v — вартість переміщення плитки в горизонтальному і вертикальному напрямках. Обидва значення c_h і c_v менші . Наступні три рядки задають початкове розташування, а останні три рядки — фінальне у такому форматі:
d_A\ d_B\ d_C
d_D\ d_E\ d_F
d_G\ d_H\ d_I
Кожен рядок містить три цифри, розділені пробілом. Цифра d_X ( — одна з літер від до ) вказує на стан квадрата , як показано на Рисунку 2. Цифри 1, \ldots, 8 вказують на номер плитки у квадраті. Цифра означає, що квадрат порожній.
Останній рядок містить два нулі і не обробляється.
Для кожного тесту виведіть в окремому рядку найменшу вартість, за яку можна отримати кінцевий стан. Загальна вартість дорівнює сумі вартостей ходів усіх плиток з початкового стану в кінцевий.
Приклад 1