题意太杀了，而且根本没法往状压 DP 方面想……
首先，补充题意：同一时刻只能移动一个骑士！
第二，八方移动下，两点最短路是切比雪夫距离。
考虑到骑士间互不干涉，可以对于每个骑士独立地计算再合并。
（如果有别的骑士挡路可以直接避开，其他避不开的肯定不是最优解。）
骑士仅会停留在初始位置或是某个人质的位置。
设 \(f_{i,S,j}\) 表示第 \(i\) 个骑士俘获的人质构成 \(S\) 集合，最后俘获的是 \(j\)。
转移时，枚举 \(i,S,j\) 和将要俘获的人质 \(k\)，那么有转移： \[f_{i,S \bigcup \{ k \},k} = \min f_{i,S,j} + dis(p_j,p_k)\]
其中 \(p_i\) 表示第 \(i\) 个人质的坐标，\(dis(x,y)\) 表示 \(x,y\) 的切比雪夫距离。
然后考虑合并答案，设 \(g_{i,S}\) 表示前 \(i\) 个骑士共拯救了集合 \(S\) 内的人质。
枚举 \(i,S\) 和这个骑士俘获的人质 \(S' \subseteq S\) 和他最后俘获的人质 \(j\)。
有 \[g_{i,S} = \min g_{i - 1,S - S'} + f_{i,S',j}\]
注意一些初值。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
const int N = 10;
const int W = 8;
int T;
int n,m,full;
int K[N + 5][2],P[N + 5][2];
int f[N + 5][(1 << N) + 5][N + 5];
int g[N + 5][(1 << N) + 5];
int ans;
char s[W + 5][W + 5];
int main()
{
scanf("%d",&T);
while(T--)
{
n = m = 0,memset(f,0x3f,sizeof f),memset(g,0x3f,sizeof g),g[0][0] = 0,ans = 0x3f3f3f3f;
for(register int i = 1;i <= W;++i)
{
scanf("%s",s[i] + 1);
for(register int j = 1;j <= W;++j)
if(s[i][j] == 'K')
K[++n][0] = i,K[n][1] = j;
else if(s[i][j] == 'P')
P[++m][0] = i,P[m][1] = j;
}
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
f[i][1 << j - 1][j] = dis(K[i][0],K[i][1],P[j][0],P[j][1]);
full = (1 << m) - 1;
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= full;++j)
for(register int k = 1;k <= m;++k)
if(!(j & (1 << k - 1)))
for(register int l = 1;l <= m;++l)
if(j & (1 << l - 1))
f[i][j | (1 << k - 1)][k] = min(f[i][j | (1 << k - 1)][k],f[i][j][l] + dis(P[l][0],P[l][1],P[k][0],P[k][1]));
for(register int i = 1;i <= n;++i)
for(register int j = 0;j <= full;++j)
{
g[i][j] = g[i - 1][j];
for(register int k = 0;k <= j;++k)
if((k & j) == k)
for(register int l = 1;l <= m;++l)
if(k & (1 << l - 1))
g[i][j] = min(g[i][j],g[i - 1][j ^ k] + f[i][k][l]);
}
printf("%d\n",g[n][full]);
}
}