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

Головоломка

Головоломка

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

Васі подобається гратись з усілякими головоломками. Одну з них показано на рисунку. Вона являє собою прямокутну коробку з трьома однаковими квадратними вирізами зі сторонами, паралельними сторонам коробки. Розміщення вирізів симетричне, як можна бачити з рисунку. В результаті у коробці утворюється нескладна система коридорів. У цих коридорах лежать чорні та білі кулі, діаметр кожної з них дорівнює 1. Ширина коридору та довжина сторони квадратного вирізу також рівні 1. Розміри коробки – 7×3, як показано на рисунку.

Гра полягає у наступному. Дозволяється за один хід зсувати кулі, розміщені навколо довільного з вирізів, на одну позицію за годиниковою стрілкою навколо цього вирізу. Задано початкове розміщення куль у головоломці. Потрібно за найменшу кількість ходів отримати інше задане розміщення куль.

Вхідні дані

Спочатку у файлі зображено початковий стан головоломки. При цьому біла куля позначається буквою 'w', чорна – буквою 'b', а квадрат вирізу показано пропуском. Нижче наведено приклад вхідного файлу, який відповідає рисунку. Після зображення початкового стану йде порожній рядок, після чого у такому ж форматі наведено зображення стану, який необхідно отримати.

Вихідні дані

У якості відповіді виведіть кількість ходів або -1, якщо розв'язати задачу неможливо.

Приклад

Вхідні дані #1
bwwwbww
w w w b
wwbwbww

wwbwbww
w w w b
bwwwbww
Вихідні дані #1
2
Джерело Orel STU & Udmurt SU Contest, Petrozavodsk, Thursday, September 1, 2005