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:
- '
0' — denotes empty cell; - '
1' — denotes cell with obstacle; - '
K' — denotes white king; - '
P' — denotes black pawn.
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 | |
|
| 2 | |
|