[luoguP2324] [SCOI2005]骑士精神（A*？）

传送门

蒟蒻并不懂A*是什么，但是题解里有个Astar

可以看出，当前棋盘和最终的棋盘如果有k个不同的，那么至少需要k-1步来移动

所以如果 当前步数 + k - 1 > limit 就直接退出

然后当然就是用喜闻乐见的迭代加深搜索啦，广搜占空间那么大又难写

最后吐槽一句，为什么我加哈希判重反而比不判重慢。。？

#include <cstdio>
#define swap(x, y) ((x) ^= (y) ^= (x) ^= (y)) 
#define P 1000007

int T, limit;
char s[6][6], t[6][6];
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1},
	dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
bool vis[P];

inline bool dfs(int k)
{
	int i, j, sx, sy, x, y, cnt = 0, hash = 0;
	for(i = 1; i <= 5; i++)
		for(j = 1; j <= 5; j++)
		{
			hash = (hash * 17 + s[i][j]) % P;
			cnt += (s[i][j] != t[i][j]);
			if(s[i][j] == '*')
				sx = i, sy = j;
		}
	if(!cnt) return 1;
	cnt--;
	if(k > limit) return 0;
	if(vis[hash]) return 0;
	if(k + cnt - 1 > limit) return 0;
	for(i = 0; i < 8; i++)
	{
		x = sx + dx[i];
		y = sy + dy[i];
		if(1 <= x && x <= 5 && 1 <= y && y <= 5)
		{
			swap(s[sx][sy], s[x][y]);
			if(dfs(k + 1)) return 1;
			swap(s[sx][sy], s[x][y]);
		}
	}
	return 0;
}

int main()
{
	int i, j;
	scanf("%d", &T);
	t[1][1] = '1', t[1][2] = '1', t[1][3] = '1', t[1][4] = '1', t[1][5] = '1';
	t[2][1] = '0', t[2][2] = '1', t[2][3] = '1', t[2][4] = '1', t[2][5] = '1';
	t[3][1] = '0', t[3][2] = '0', t[3][3] = '*', t[3][4] = '1', t[3][5] = '1';
	t[4][1] = '0', t[4][2] = '0', t[4][3] = '0', t[4][4] = '0', t[4][5] = '1';
	t[5][1] = '0', t[5][2] = '0', t[5][3] = '0', t[5][4] = '0', t[5][5] = '0';
	vis[151603] = 1;
	while(T--)
	{
		limit = 0;
		for(i = 1; i <= 5; i++)
			scanf("%s", s[i] + 1);
		while(limit <= 15)
		{
			if(dfs(1))
			{
				printf("%d
", limit);
				break;
			}
			limit++;
		}
		if(limit > 15) puts("-1");
	}
	return 0;
}