BZOJ 1085 [SCOI2005]骑士精神

题目大意

给你一个5x5的国际象棋棋盘，上面有很多马。有一些是白子，有一些是黑子(大人の姉妹)，还有一个位置是空的，求需要多少步可以使得整个棋盘变成某个“特定状态”。

这道题看到数据范围——不是状压DP就是DFS（还有随机化。 所以就可以用DFS尝试解决。 但是如果暴力D的话是D不出来的qwq所以就要进行优雅的优化qwq

A*算法的最终目的只有通过剪枝来加速，而不是什么蛇皮的特殊算法

我们把“距离最终状态还有多少点不同”作为Astar启发函数，因为每一次最多只有1个点可以回到原地。之后如果现在的Astar()已经超出我的最大预估答案了我就没有必要继续下去了，剪掉。

#include <cstdio>
#include <algorithm>
using namespace std;
int T,ans,dirx[]={1,1,-1,-1,2,2,-2,-2},diry[]={2,-2,2,-2,1,-1,1,-1};
char s[6][6],tg[6][6]={{"11111"},{"01111"},{"00*11"},{"00001"},{"00000"}};
int astar(int tx)
{
	 for(int i=0;i<5;++i)
        for(int j=0;j<5;++j) tx+=(s[i][j]!=tg[i][j]);
    return tx;
}
inline bool check(int tx,int ty) {return tx>=0&&tx<5&&ty>=0&&ty<5;}
void dfs(int depth,int tx,int ty)
{
	if(astar(depth)>ans) return;
	if(astar(depth)==depth)
	{
		ans=depth;
		return;
	}
	for(int i=0;i<8;++i)
		if(check(tx+dirx[i],ty+diry[i]))
		{
			swap(s[tx][ty],s[tx+dirx[i]][ty+diry[i]]);
			dfs(depth+1,tx+dirx[i],ty+diry[i]);
			swap(s[tx][ty],s[tx+dirx[i]][ty+diry[i]]);
		}
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		ans=16;
		int tx,ty;
		for(int i=0;i<5;++i) scanf("%s",s[i]);
		for(int i=0;i<5;++i)
			for(int j=0;j<5;++j)
				if(s[i][j]=='*')
					tx=i,ty=j;
		dfs(0,tx,ty);
		printf("%d\n",ans>15?-1:ans); 
	}
}