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

Шахматы

Шахматы

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

Во многих видах спортивных соревнований имеются различные ритуалы, направленные для примирения конкурирующих команд или игроков. Это может быть рукопожатие, поклон или даже разбрызгивание шампанского. ACM (Alliance of Chess Masters) собирается создать свой собственный ритуал, шахматную миниигру, в которой участвует два игрока в союзе друг с другом (а не как обычно, друг против друга). Игра проходит на шахматной доске размером 3x3, у каждого из игроков имеется два шахматных коня, которых они должны переместить так, чтобы добраться от одной позиции до другой (игроки могут делать шаги в любом порядке, не обязательно по очереди). При этом два коня не могут занимать одну и ту же клетку.

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

Giriş verilənləri

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

Çıxış verilənləri

Для каждого теста выведите одно целое число – сложность задачи. Если задача не имеет решения, то вывести -1.

Nümunə

Giriş verilənləri #1
2
WBB ..W   
W.. ..W
... .BB

..B ..B
W.B ..B
W.. WW.
Çıxış verilənləri #1
4
-1
Mənbə Школа Программиста, Красноярский край, Пятая командная олимпиада, 15 ноября 2009, Задача C