Піщані черви Бленджіла та Кольорові звиви
Піщані черви Бленджілу повзають по піщаній поверхні планети Бленджіл. Як єдині відомі мешканці планети, вони захищають свою батьківщину, атакуючи та пожираючи знизу всіх, хто ступає на їхню планету.
Звісно, піщані черви повинні бути сильними, гнучкими та здатними повзати якомога тихіше. Усі підлітки-черви призиваються на шестимісячний навчальний табір, де вони проходять інтенсивну підготовку. Найвимогливішим з тренувальних вправ є відомий "тест на звивання", який вимагає від курсантів-червів повзти з однієї позиції до паралельної позиції на кілька сотень футів далі. Лише найміцніші та найрішучіші черви виживають.
Ця вправа настільки відома, що CS101 Академії Джедаїв змушує своїх студентів розв'язувати головоломку, засновану на Навчальному таборі Бленджілу. І ця головоломка виглядає приблизно так:
Дано n×m дошку (3 ≤ n ≤ 6, 5 ≤ m ≤ 50), на якій потрібно звивати піщаного черва Бленджілу (довжиною n) з лівого стовпця до правого, забезпечуючи, щоб черв ніколи одночасно не займав дві клітинки одного кольору.
Розгляньте наступну 3×5 дошку, де кожне число представляє різний колір, а черв зображений ланцюгом кіл:
Один з двох можливих ходів - це потягнути нижню частину черва вправо, щоб він був розташований наступним чином:
Тепер ми можемо потягнути з іншого кінця черва, щоб провести його через три різні позиції:
Через серію додаткових ходів можна звивати черва в цільову позицію, де тіло черва повністю знаходиться в крайньому правому стовпці:
Допустимо, щоб черв досяг правого стовпця в будь-якій орієнтації.
Ваше завдання - написати програму, яка зчитує серію дощок, описаних вище, і для кожної виводить мінімальну кількість звивань, необхідних для переміщення черва з лівого стовпця до правого (або -1, якщо рішення немає).
Вхідні дані
Дані будуть представлені у вигляді n рядків з m елементами. У кожному рядку будуть цифри, що представляють колір (кольори представлені цифрами від 1 до 7 - не всі дошки використовуватимуть усі 7 кольорів). Кольори в крайньому лівому стовпці кожної вхідної дошки гарантовано унікальні. Кожна дошка відокремлена від наступної порожнім рядком. Кінець введення буде позначено окремим "end". Між останньою дошкою та "end" буде порожній рядок.
Вихідні дані
Для кожної зчитаної дошки виведіть мінімальну кількість звивань, необхідних для переміщення черва з лівого стовпця до правого (або "-1", якщо рішення немає), після чого новий рядок.
