[SCOI2005]骑士精神

题目

BZOJ

做法

爆搜是肯定的，考虑剪枝
(g(n)+h(n)=f(n))，(h)为不同点个数

My complete code

#include<bits/stdc++.h>
using namespace std;
typedef int LL;
const LL dx[]={0,1,1,-1,-1,2,2,-2,-2};
const LL dy[]={0,2,-2,2,-2,1,-1,1,-1};
const LL goal[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}
};
LL n,m,a[7][7],ok;
char ch;
inline LL Check(){
    LL ret=0;
    for(LL i=1;i<=5;i++)
        for(LL j=1;j<=5;j++)
            ret+=(a[i][j]!=goal[i][j]);
    return ret;
}
inline bool Be(LL x,LL y){
    if(x<1||x>5||y<1||y>5) return false;
    return true;
}
inline void A_star(LL dep,LL x,LL y,LL Md){
    if(dep==Md){
        if(!Check())
		    ok=true;
        return;
    }
    for(LL i=1;i<=8;i++){
        LL xx(x+dx[i]),yy(y+dy[i]);
        if(!Be(xx,yy)) continue;
        swap(a[x][y],a[xx][yy]);
        LL ret=Check();
        if(ret+dep<=Md)
            A_star(dep+1,xx,yy,Md);
        if(ok) return;
        swap(a[x][y],a[xx][yy]);
    }
}
int main(){
	LL T;
	cin>>T;
    while(T--){
        LL sx(0),sy(0);
        ok=false;
        for(LL i=1;i<=5;i++){
            for(LL j=1;j<=5;j++){
            	char ch; scanf(" %c",&ch);
                if(ch=='*')
				    a[i][j]=2,sx=i,sy=j;
                else 
				    a[i][j]=ch-'0';
            }
        }
        if(!Check()){
		    puts(0);
			continue;
		}
		bool f(false);
        for(LL d=1;d<=15;++d){
            A_star(0,sx,sy,d);
            if(ok){
			    cout<<d<<endl;
			    f=true;
			    break;
			}
        }
        if(!f)
            cout<<-1<<endl;
    }return 0;
}