Задача J. Chess with obstacles

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Юные программисты Джо и Бо сидели на скучной лекции и решили сыграть в собственную версию шахмат.

На шахматном поле размера 8 × 8 располагается белый король, чёрная пешка и некоторое количество препятствий. Белые ходят первыми. Чёрная пешка ходит сверху вниз ровно на одну клетку, а король может ходить на любую соседнюю клетку (см. изображение):

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

Джо и Бо хотят определить по начальному положению фигур, кто выиграет и, если выиграют белые, то какое минимальное количество ходов для этого потребуется. Гарантируется, что на пути пешки не будет препятствий. Белые всегда ходят первые. Пропуск хода возможен только при отсутствии доступных клеток для хода.

Формат входных данных

Входные данные содержат 8 строк, каждая из которых содержит 8 символов. Символы имеют следующие значения:

Формат выходных данных

Выведите минимальное количество ходов, необходимое королю, чтобы "съесть" пешку, либо  − 1, если белый король не успеет "съесть" чёрную пешку до того, как она дойдёт до нижней горизонтали.

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

Стандартный вход Стандартный выход
1
00000001
00000000
00000000
0P00K000
00000000
00100000
00001000
00000000
3
2
00000000
00000000
00000000
00000000
000K0000
00000000
000P0000
00000000
-1

0.410s 0.232s 17