首页 > ACM题库 > HDU-杭电 > hdu 2799 Chess待解决[解题报告]C++
2014
02-14

hdu 2799 Chess待解决[解题报告]C++

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,也要很久才能得出结果,本人亲测