2014
02-14

# 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.

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.

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

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

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

6
20
9

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测