鄙人不才，使用折半搜索，思路是将棋盘状态压缩成二进制并单独记录空位。

我原本怕复杂度太大，只敢从目标状态预处理出 $8$ 步以内的状态，然后从询问状态走 $7$ 步以内检验能否对接。喜提 WA $50$ 分。后来把目标状态的 $8$ 调成 $11$, 就 AC 了？请问大佬们为什么？

#include <bits/stdc++.h>
using namespace std;
int T, n, m, ans;
char s[10][10];
int sx[] = {-2, -2, -1, -1, 1, 1, 2, 2};
int sy[] = {-1, 1, -2, 2, 2, -2, -1, 1};
map<int, int> mp[15][15];
map<int, bool> pp[15][15];
int get(int x, int y)
{
	return x * 5 + y;
}
void dfs(int t, int x, int y, int z)
{
	if(t == 12 || (mp[x][y][z] && mp[x][y][z] <= t)) return ; // 在这里从9改成了12
	mp[x][y][z] = t;
	int lp = get(x, y);
	for(int i = 0; i < 8; i++)
	{
		int X = x + sx[i], Y = y + sy[i], pos = get(X, Y), Z = z;
		if(X < 0 || X > 4 || Y < 0 || Y > 4) continue;
		if((Z >> pos) & 1) 
		{
			Z = Z &~(1 << pos), Z |= (1 << lp);
			dfs(t + 1, X, Y, Z);
		}
		else
		{
			dfs(t + 1, X, Y, Z);
		}
	}
}
void ddd(int t, int x, int y, int z)
{
	if(t == 7) return ;
	if(mp[x][y][z]) 
		ans = min(ans, t + mp[x][y][z] - 1);
	int lp = get(x, y);
	for(int i = 0; i < 8; i++)
	{
		int X = x + sx[i], Y = y + sy[i], pos = get(X, Y), Z = z;
		if(X < 0 || X > 4 || Y < 0 || Y > 4) continue;
		if((Z >> pos) & 1) 
		{
			Z = Z &~(1 << pos), Z |= (1 << lp);
			ddd(t + 1, X, Y, Z);
		}
		else
		{
			ddd(t + 1, X, Y, Z);
		}
	}
}
signed main()
{
	dfs(1, 2, 2, 549855);
	scanf("%d", &T);
	while(T--)
	{
		for(int i = 0; i <= 4; i++)
			for(int j = 0; j <= 4; j++)
				pp[i][j].clear();
		ans = 1e9;
		for(int i = 0; i < 5; i++) scanf("%s", s[i]);
		int x = 0, y = 0, z = 0;
		for(int i = 0; i < 5; i++)
		{
			for(int j = 0; j < 5; j++)
			{
				if(s[i][j] == '*') x = i, y = j;
				if(s[i][j] == '1') z += (1 << get(i, j));
			}
		}
		ddd(0, x, y, z);
		if(ans <= 15) printf("%d\n", ans);
		else printf("-1\n");
	}
	return 0;
}