Задача B. Эндшпиль: Ладья и король против короля

Автор:А. Кленин   Ограничение времени:10 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

На шахматной доске расположены белый король, белая ладья и чёрный король. Известно также, какая сторона ходит первой. Требуется найти минимальное количество полуходов, которые требуются белым, чтобы поставить мат, или определить, что это невозможно.

Формат входного файла

Число 1, если первыми ходят белые, 2 — если чёрные. Далее идут три описания позиции, разделённые пробелом: позиция белого короля, белой ладьи и чёрного короля. Позиция состоит из двух символов — вертикаль от a до h и горизонталь от 1 до 8 (например, d5). Все позиции различны.

Формат выходного файла

Выходной файл должен содержать единственное число — количество полуходов, или -1, если мат из данной позиции невозможен.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 b3 b6 a1
3
2
2 b4 c2 d1
-1

0.058s 0.012s 15