Задача J. Chess with obstacles ≡

Условие

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

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

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

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

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

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

• '0' — обозначает пустую клетку;
• '1' — обозначает клетку с препятствием;
• 'K' — обозначает белого короля;
• 'P' — обозначает чёрную пешку.

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

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

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

00000001
00000000
00000000
0P00K000
00000000
00100000
00001000
00000000

3

00000000
00000000
00000000
00000000
000K0000
00000000
000P0000
00000000

-1