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;

}