Chess

You are given a standard 8*8 chess board. There are only pawns and kings on the board. In each move, a king can move to any of its 8 neighboring cells. If you move a king into a cell occupied by a pawnn, the king will capture that pawn. You can never move a king outside the board or into a cell already occupied by another king.

Now the problem is, what is the minimal number of moves required for the kings to capture all the powns?

There are multiple cases (no more than 100).

There are exactly 8 lines for each case, representing the chess board. Each line has 8 characters. The '.' character represents an empty cell, 'P' represents a cell occupied by a pawn, and 'K' represents a cell occupied by a king.

For each board, the number of kings and the number of pawn are between 1 and 10, both inclusive.

Each case is followed by an empty line.

For each case, output the minimal number of moves required for the kings to capture all the powns.

.PPPPKP.
........
........
........
........
........
........
........

P......P
........
........
........
...KK...
........
........
P......P

.....P.P
..K....P
....K...
..PP...P
...K..KK
........
K.......
KP.K....

6
20
9

hhanger@zju

HDOJ 2009 Summer Exercise（5）