BZOJ 1085 SCOI2005 騎士精神 IDA*

BZOJ 1085 SCOI2005 騎士精神 IDA*

題目大意：給定一個棋盤，每個棋子都是騎士，問能否在15步之內移動為特定排布

此題采用IDA*

估價函數為：當前棋盤與目標棋盤不同的位置數量-1

易知一個棋盤最少需要這麼多的步數才能達成目標棋盤

若當前步數+估價函數大於最大深度 則剪枝

優先搜索懶得寫0.0 這樣就能切掉就行

#include
#include
#include
#include
using namespace std;
int max_dpt,flag;
char map[6][6];
const int dx[]={1,1,-1,-1,2,2,-2,-2};
const int dy[]={2,-2,2,-2,1,-1,1,-1};
char tar[6][7]={
	"000000",
	"011111",
	"001111",
	"000*11",
	"000001",
	"000000"
};
inline char Get_Char()
{
	char c;
	do c=getchar(); while(c!='0'&&c!='1'&&c!='*');
	return c;
}
int Evalute()
{
	int i,j,re=0;
	for(i=1;i<=5;i++)
		for(j=1;j<=5;j++)
			re+=map[i][j]!=tar[i][j];
	return re-1;
}
void IDA8(int dpt,int x,int y)
{
	int i,temp=Evalute();
	if(temp==-1)
	{
		flag=1;
		return;
	}
	if(temp+dpt>max_dpt)
		return ;
	for(i=0;i<8;i++)
	{
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx<=0||yy<=0||xx>5||yy>5)
			continue;
		swap(map[x][y],map[xx][yy]);
		IDA8(dpt+1,xx,yy);
		swap(map[x][y],map[xx][yy]);
		if(flag)
			return ;
	}
}
int main()
{
	int T,i,j,x,y;
	for(cin>>T;T;T--)
	{
		flag=0;
		for(i=1;i<=5;i++)
			for(j=1;j<=5;j++)
			{
				map[i][j]=Get_Char();
				if(map[i][j]=='*')
					x=i,y=j;
			}
		for(max_dpt=0;max_dpt<=15;max_dpt++)
		{
			IDA8(0,x,y);
			if(flag)
				break;
		}
		if(max_dpt==16)
			max_dpt=-1;
		cout<