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

Шахи

Шахи

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

У багатьох видах спортивних змагань існують різноманітні ритуали, направлені на примирення конкуруючих команд або гравців. Це може бути рукотискання, поклін або навіть розбризгування шампанского. ACM (Alliance of Chess Masters) збирається створити свій власний ритуал, шахову мінігру, у які приймає участь два гровці у союзі один з одним (а не як звичайно, один проти іншого). Гра проходить на шаховій дошці розміром 3x3, у кожного з гравців є два шахових коня, яких вони повинні перемістити так, щоб дістатись від однієї позиції до іншої (гравці можуть робити ходи у довільному порядку, не обов'язково по черзі). При цьому два коня не можуть займати одну й ту ж клітину.

Стартові та кінцеві положення визаначаються суддею. Виявляється, що деякі такі задачі є більш важкими, ніж інші, а деякі можуть бути навіть невирішувані - тому, деякі гравці інколи не здатні завершити ритуал. Ваша задача полягає у тому, щоб написати програму, яка за заданим положенням початкової і кінцевої позиції, зможе визначити можливість успішного закінченгя гри, а у випадку успіху зможе також визначити складність задачі – мінімально можливу кількість ходів, потрібних для розв'язання даної задачі.

Вхідні дані

Складається з декількох тестів, у кожному з яких 3 рядки по 7 символів. Перші 3 символи кожного рядка описують відповідний рядок шахового рядка для початкової позиції, далі йде пропуск і останні 3 символи, які описують аналогічним чином рядок кінцевої позиції. Білий кінь позначається символом «W», а чорний – символом «B», пусті клітинки позначаються «.» (точкою). Тестові випадки відокремліні один від одного пустим рядком. Кількість тестів вказано у першому рядку.

Вихідні дані

Для кожного тесту вивести одне ціле число – складність задачі. Якщо задача не має розв'язку, то вивести -1.

Приклад

Вхідні дані #1
2
WBB ..W   
W.. ..W
... .BB

..B ..B
W.B ..B
W.. WW.
Вихідні дані #1
4
-1
Джерело Школа Программиста, Красноярский край, Пятая командная олимпиада, 15 ноября 2009, Задача C