代码by gn,题解by hansang：

#include<bits/stdc++.h>
using namespace std;
const int N=15;
char s[N];
struct node{int x, y;} a[N], b[N];
int lena, lenb, dp[N][1<<N], f[N][N][1<<N];
//a数组存骑士方位，b数组存人质，dp[i][j]表示当前移动骑士i俘获了j集合的人质
//f[x][y][S]表示S集合中一条终点为(x, y)的最短路径
int get_dis(node n1, node n2){
    return max(abs(n1.x-n2.x), abs(n1.y-n2.y));
    //因为可以走八个方向，所以这样求最短距离
}
int calc(node no, int S){ //使用记忆化搜索
    int x=no.x, y=no.y;
    if(f[x][y][S]>=0) return f[x][y][S];
    if(S==0) return f[x][y][S]=0;
    int res=1e9;
    for(int i=1; i<=lenb; i++) if((1<<(i-1))&S){
        res=min(res, calc(b[i], S^(1<<(i-1)))+get_dis(no, b[i]));
        //从S集合中再挑一个点，先求S集合中一条终点为那个点的最短路径，再加上那个点到当前点的距离
    }
    return f[x][y][S]=res;
}
int main(){
    int T; scanf("%d", &T);
    while(T--){
        lena=lenb=0; //多组数据清0很重要
        for(int i=1; i<=8; i++){
            scanf("%s", s+1);
            for(int j=1; j<=8; j++){if(s[j]=='K') a[++lena]={i, j}; 
                if(s[j]=='P') b[++lenb]={i, j};
            }
        }

        memset(dp, 0x3f, sizeof(dp));
        memset(f, -1, sizeof(f));
        for(int i=0; i<(1<<lenb); i++) 
            dp[1][i]=calc(a[1], i); //骑士1特殊赋值

        for(int i=2; i<=lena; i++){
            for(int j=0; j<(1<<lenb); j++){
                for(int k=0; k<(

代码by gn,题解by hansang：

#include<bits/stdc++.h>
using namespace std;
const int N=15;
char s[N];
struct node{int x, y;} a[N], b[N];
int lena, lenb, dp[N][1<<N], f[N][N][1<<N];
//a数组存骑士方位，b数组存人质，dp[i][j]表示当前移动骑士i俘获了j集合的人质
//f[x][y][S]表示S集合中一条终点为(x, y)的最短路径
int get_dis(node n1, node n2){
    return max(abs(n1.x-n2.x), abs(n1.y-n2.y));
    //因为可以走八个方向，所以这样求最短距离
}
int calc(node no, int S){ //使用记忆化搜索
    int x=no.x, y=no.y;
    if(f[x][y][S]>=0) return f[x][y][S];
    if(S==0) return f[x][y][S]=0;
    int res=1e9;
    for(int i=1; i<=lenb; i++) if((1<<(i-1))&S){
        res=min(res, calc(b[i], S^(1<<(i-1)))+get_dis(no, b[i]));
        //从S集合中再挑一个点，先求S集合中一条终点为那个点的最短路径，再加上那个点到当前点的距离
    }
    return f[x][y][S]=res;
}
int main(){
    int T; scanf("%d", &T);
    while(T--){
        lena=lenb=0; //多组数据清0很重要
        for(int i=1; i<=8; i++){
            scanf("%s", s+1);
            for(int j=1; j<=8; j++){
                if(s[j]=='K') a[++lena]={i, j}; 
                if(s[j]=='P') b[++lenb]={i, j};
            }
        }

        memset(dp, 0x3f, sizeof(dp));
        memset(f, -1, sizeof(f));
        for(int i=0; i<(1<<lenb); i++) 
            dp[1][i]=calc(a[1], i); //骑士1特殊赋值

        for(int i=2; i<=lena; i++){
            for(int j=0; j<(1<<lenb); j++){
                for(int k=0; k<(1<<lenb); k++) if((j&k)==k){
                    int t=calc(a[i], j^k);
                    dp[i][j]=min(dp[i][j], dp[i-1][k]+t);
                    //分成两部分，一部分在上一个骑士解决，一部分当前骑士走
                }
            }
        }
        printf("%d\n", dp[lena][(1<<lenb)-1]);
    }
    return 0;
}