IDA*

算初学吧.很裸的IDA*

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int map[6][6];
int aim[6][6]={	{0,0,0,0,0,0},
				{0,1,1,1,1,1},
				{0,0,1,1,1,1},
				{0,0,0,2,1,1},
				{0,0,0,0,0,1},
				{0,0,0,0,0,0}};
int dx[9]={1,1,2,2,-1,-1,-2,-2};
int dy[9]={-2,2,1,-1,2,-2,-1,1};
int judge()
{
	int res=0;
	for(int i=1;i<=5;i++)
		for(int j=1;j<=5;j++)
			if(map[i][j]!=aim[i][j])
				res+=1;
	return res;
}
bool make_it;
bool check(int x,int y)
{
	if(x<=0||y<=0||x>=6||y>=6)
		return false;
	return true;
}
void IDA_star(int x,int y,int dir,int dep,int want)
{
	int nxt=judge();
	if(!nxt)
	{	
		cout<<dep<<endl;
		make_it=true;
	}
	if(dep+nxt-1>want)
		return ;
	for(int i=0;i<=7;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(!check(nx,ny))
			continue;
		swap(map[x][y],map[nx][ny]);
		IDA_star(nx,ny,i,dep+1,want);
		swap(map[x][y],map[nx][ny]);
		if(make_it)
			return ;
	}
}
int main()
{
	cin.sync_with_stdio(false);
	int n;
	cin>>n;
	while(n--)
	{
		make_it=false;
		int beginx,beginy;
		char in;
		for(int i=1;i<=5;i++)
			for(int j=1;j<=5;j++)
			{
				cin>>in;
				switch(in)
				{
					case '0':map[i][j]=0;break;
					case '1':map[i][j]=1;break;
					case '*':map[i][j]=2;beginx=i;beginy=j;break;
				}
			}
		for(int i=1;i<=15;i++)
			if(!make_it)
				IDA_star(beginx,beginy,8,0,i);
		if(!make_it)
			cout<<"-1"<<endl;	
	}
}