$RT$

好像只有我一个人打的是广搜

所有都输出 $-1$。

#include<iostream>
#include<queue>
#include<map>
using namespace std;
map<unsigned, bool> hmz;
const int need[6][6] = {
	{0,0,0,0,0,0},
	{0,1,1,1,1,1},
	{0,0,1,1,1,1},
	{0,0,0,-1,1,1},
	{0,0,0,0,0,1},
	{0,0,0,0,0,0}
};
const int dx[] = { 1,1,-1,-1,2,2,-2,-2 }, dy[] = { 2,-2,2,-2,1,-1,1,-1 };
int T, beg[26], tmp[26];
unsigned geth(int now[])
{
	unsigned ans = 0;
	for (int i = 1; i <= 25; i++)
		ans = ans * 121 + now[i];
	return ans;
}
int get(int x, int y)
{
	return (x - 1) * 5 + y;
}
int check(const int now[])
{
	int cnt = 0;
	for (int i = 1; i <= 5; i++)
	{
		for (int j = 1; j <= 5; j++)
		{
			if (need[i][j] != now[get(i, j)])
				++cnt;
		}
	}
	return cnt;
}
struct node
{
	int step;
	int now[26];
	bool operator<(const node& A) const
	{
		return step + check(now) > A.step + check(A.now);
	}
};
priority_queue<node> q;
void cover(node &x, int now[])
{
	for (int i = 1; i <= 25; i++)
		x.now[i] = now[i];
}
void insert(int step, int now[])
{
	node tmp;
	tmp.step = step;
	cover(tmp, now);
	q.push(tmp);
}
void bfs()
{
	hmz[geth(beg)]=true;
	insert(0, beg);
	while (!q.empty())
	{
		node now = q.top();
		if (now.step+check(now.now) > 16)
		{
			q.pop();
			continue;
		}
		if (check(now.now) == 0)
		{
			cout << now.step << endl;
			return;
		}
		int nx, ny;
		for (int i = 1; i <= 5; i++)
			for (int j = 1; j <= 5; j++)
				if (now.now[get(i, j)] == -1)
					nx = i, ny = j;
		for (int i = 0; i < 8; i++)
		{
			int tx = nx + dx[i], ty = ny + dy[i];
			if (tx >= 1 && tx <= 5 && ty >= 1 && ty <= 5)
			{
				tmp[0] = 0;
				for (int j = 1; j <= 25; j++)
					tmp[j] = now.now[j];
				swap(tmp[get(nx, ny)], tmp[get(tx, ty)]);
				if (!hmz[geth(tmp)])
				{
					hmz[geth(tmp)] = true;
					insert(now.step + 1, tmp);
				}
			}
		}
		q.pop();
	}
	cout << -1 <<endl;
}
int main()
{
	cin >> T;
	while (T--)
	{
		hmz.clear();
		for (int i = 1; i <= 5; i++)
			for (int j = 1; j <= 5; j++)
			{
				char u;
				cin >> u;
				if (u == '*')
					beg[get(i,j)] = -1;
				else
					beg[get(i,j)] = u - '0';
			}
		bfs();
	}
	return 0;
}