Problem J. Chess with obstacles

Input file:Standard input   Time limit:1 sec
Output file:Standard output   Memory limit:512 Mb

Statement

Young programmers Joe and Boe were sitting at the boring lecture and decided to play their own version of chess.

The chess board of size 8 × 8 contains white king, black pawn and some obstacles. White moves first. Black pawn can move exactly one cell down from top to bottom. and white king can move to any neighboring cell (see picture):

Some cells are occupied by obstacles. If the cell contains an obstacle, white king can not move to that cell. If king moves to the cell containing the pawn, then the pawn is captured. The goal of white is to capture the black pawn before it moves to the bottom row. The goal of the black is to get to the bottom row and not to be captured before that by white king.

Joe and Boe want to determine, given the staring position of the pieces, who will win, and if the winner is white, what is the minimum number of moves required. It is guaranteed that there are now obstacles on the path of black pawn. It is possible to skip the move, but only if there are no allowed cells to move to.

Input format

Input contains 8 lines, each line contains 8 characters. Characters have the following meanings:

Output format

Output minimum number of moves, required for the white king to capture the pawn, or  − 1 if the white king will not be able to capture the black pawn before it reaches the bottom row.

Sample tests

No. Standard input Standard output
1
00000001
00000000
00000000
0P00K000
00000000
00100000
00001000
00000000
3
2
00000000
00000000
00000000
00000000
000K0000
00000000
000P0000
00000000
-1

0.372s 0.149s 15