|
Что делал слон, когда пришёл на поле он?
Какой слон? Белый? Ясно. А на какое вообще поле он шёл? А... e8. Понятно. И сколько ему понадобилось для этого ходов? Шесть? Так много? А что ему мешало попасть туда раньше? Далеко стоял? Но ведь известно, что из любой клетки слон может попасть в любую другую не более чем за два хода (если вообще может). Он был не один? Три чёрные пешки ему мешали? Вот дела...
Ваша задача - определить минимальное количество ходов, необходимых белому слону для того, чтобы попасть в заданную клетку. Учтите, что на доске также расположены три чёрные пешки, цель которых - задержать слона на максимально возможное количество ходов.
Слон и пешки ходят по очереди (первым ходит слон). Слон не может ходить под рубку. Все фигуры ходят по шахматным правилам. Если пешка находится на седьмой горизонтали, то она может сходить как на шестую, так и на пятую горизонтали. Слон ходит по диагонали на произвольное число клеток. Все клетки между началом и концом хода слона должны быть пустыми. Слон может за один ход срубить одну пешку. Если пешка добирается до первой горизонтали, то она так и остаётся там стоять. В начальной позиции пешки не могут быть расположены на восьмой горизонтали, а слон не находится под рубкой. В конечной позиции слон также не должен находиться под рубкой. Можете считать, что в случае, когда все чёрные пешки расположены на первой горизонтали или оказались срублены, ходы совершает только слон. Учтите, что если хотя бы одна чёрная пешка может сделать ход, то ход должен быть совершён.
Пусть в представленном на рисунке примере слону требуется попасть на поле c5. Тогда одна из возможных оптимальных стратегий поведения пешек: b7->b6, c5->c4, c4->c3, c3->c2. Тогда белому слону понадобится пять ходов: e3->f4, f4->d6, d6->c7, c7->b6, b6->c5.
Исходные данные
Входной файл содержит пять строк. В первой строке задана начальная позиция слона. Во второй строке задано поле, на которое пытается попасть слон. В третьей, четвёртой и пятой строке содержатся позиции чёрных пешек. Каждая позиция описывается парой символов (вертикаль; горизонталь).
Результат
Выведите в выходной файл одно число - минимальное количество ходов, необходимых слону для того, чтобы попасть в заданную клетку. Если слон не может попасть в заданную клетку, выведите "Impossible" (без кавычек с заглавной буквы).
Пример
| Исходные данные | Результат |
|---|
e3
c5
c5
d6
b7
|
5
|
b2
d4
a7
d4
d6
|
1
|
b2
с4
a7
d4
d6
|
Impossible
|
b2
b2
a7
d4
d6
|
0
|
Пояснение к примерам.
Первый пример подробно разобран выше.
Во втором примере слон первым и единственным ходом срубает пешку, расположенную в клетке d4.
В третьем примере слон никогда не сможет попасть в заданную клетку, так как, согласно шахматным правилам, она недостижима для него.
В четвёртом примере слон уже находится в нужной клетке.
| 
