Description
用字符矩阵来表示一个8x8的棋盘，'.'表示是空格，'P'表示人质，'K'表示骑士。每一步，骑士可以移动到他周围的8个方格中的任意一格。如果你移动到的格子中有人质（即'P'），你将俘获他。但不能移到出棋盘或当前是'K'的格子中。请问最少要移动多少步骑士才能俘获所有的人质。
Input Format
第一行一个整数N(<=5)，表示有多少个棋盘。即多组测试数据。每一组有8行，每行8个字符。字符只有'.',大写'P',大写'K'三种字符。'P'和'K'的个数范围都在[1,10]。
Output Format
有N行，每行只一个整数，相应棋盘俘获全部人质所需要的最少步数。
Sample Input
2
P......P
........
........
........
...KK...
........
........
P......P
.....P.P
..K....P
....K...
..PP...P
...K..KK
........
K.......
KP.K....
Sample Output
20
9
Solution
多亏参考了省队队长的代码，%yh,
可以发现骑士和人质数量极小，考虑状压DP。
虽然骑士有好多个，实际上他们不影响，可以先分别做DP，不妨让F[k][i][S]表示第k个骑士在第i个点且俘获状态为S的最少步数，易得F[k][j][S|1<<(j-1)]=min{f[k][i][S]+ptp[i][j]},其中ptp[i][j]表示人质i到人质j的最少步数
这里有个关键的地方就是骑士可以向8个方向移动，所以2点之间最少步数应为max(|x1-x2|,|y1-y2|)
然后记录每个骑士i对于状态S的最少步数，我的代码是用F[k][0][S]表示
接下来在做一次DP，用G[i][S]表示前i个骑士对于状态S的最少步数，
则G[i][S]=min{G[i-1][S^S2]+F[i][S2]},1<=S2<=最终状态，且(S | S2) == S,答案就很明显了
Code
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#define N 12
using namespace std;
struct info {
int x, y;
} k[N], p[N];
int T, knum, pnum, dis[N][N], f[N][N][1 << N], ptp[N][N], ans[N][1 << N];
inline void Init() {
memset(dis, 0, sizeof(dis));
knum = pnum = 0;
for (int i = 1; i <= 8; ++i)
for (int j = 1; j <= 8; ++j) {
char ch = getchar();
while (ch != '.' && ch != 'K' && ch != 'P') ch = getchar();
if (ch == 'K') k[++knum] = (info) {i, j};
if (ch == 'P') p[++pnum] = (info) {i, j};
}
for (int i = 1; i <= knum; ++i)
for (int j = 1; j <= pnum; ++j) {
int x1 = k[i].x, y1 = k[i].y, x2 = p[j].x, y2 = p[j].y;
dis[i][j] = max(fabs(x1 - x2), fabs(y1 - y2));
}
for (int i = 1; i <= pnum; ++i)
for (int j = i + 1; j <= pnum; ++j) {
int x1 = p[i].x, y1 = p[i].y, x2 = p[j].x, y2 = p[j].y;
ptp[i][j] = ptp[j][i] = max(fabs(x1 - x2), fabs(y1 - y2));
}
}
inline void DP(int k) {
for (int i = 1; i <= pnum; ++i)
f[k][i][1 << (i - 1)] = dis[k][i];
for (int S = 1; S < (1 << pnum); ++S)
for (int i = 1; i <= pnum; ++i)
if (S & (1 << (i - 1)))
for (int j = 1; j <= pnum; ++j)
if (!(S & (1 << (j - 1))))
f[k][j][S | (1 << (j - 1))] = min(f[k][j][S | (1 << (j - 1))], f[k][i][S] + ptp[i][j]);
}
int main() {
scanf("%d", &T);
while (T--) {
Init();
memset(f, 0x3f, sizeof(f));
for (int k = 1; k <= knum; ++k) {
DP(k);
for (int S = 1; S < (1 << pnum); ++S)
for (int i = 1; i <= pnum; ++i)
f[k][0][S] = min(f[k][0][S], f[k][i][S]);
}
memset(ans, 0x3f, sizeof(ans));
ans[0][0] = 0;
for (int i = 1; i <= knum; ++i) {
ans[i][0] = 0;
for (int S = 1; S < (1 << pnum); ++S) {
ans[i][S] = ans[i - 1][S];
for (int g = 1; g < (1 << pnum); ++g) {
if ((S | g) != S) continue;
ans[i][S] = min(ans[i][S], ans[i - 1][S ^ g] + f[i][0][g]);
}
}
}
printf("%d\n", ans[knum][(1 << pnum) - 1]);
}
return 0;
}