luogu
AcWing
同步发布于Blog

分析

IDAstar
大力推推推，易得一次只能改变一个骑士的状态
然后估价函数就很显然了

int Get()
{
    int res=0;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            if(arr[i][j]!=B[i][j]&&arr[i][j])
                res++;
    return res;
}

显然估价$<=$实际，成立
若不知道为什么估价必须小于实际，欢迎阅读

Code

#include<bits/stdc++.h>
using namespace std;
int T,ans,flag,arr[6][6],B[6][6],limit,st1,st2;
int dx[8]={-1,-2,-1,-2,1,2,1,2};
int dy[8]={-2,-1,2,1,-2,-1,2,1};
char ip;
int Get()
{
    int res=0;
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            if(arr[i][j]!=B[i][j]&&arr[i][j])
                res++;
    return res;
}
void IDAstar(int x,int y,int d)
{
    int F=Get();
    if(F+d>limit)
        return;
    if(!F)
    {
        ans=d;
        flag=1;
    }
    for(int i=0;i<8;i++)
    {
        int X=x+dx[i];
        int Y=y+dy[i];
        if(X<1||X>5||Y<1||Y>5)
            continue;
        swap(arr[x][y],arr[X][Y]);
        IDAstar(X,Y,d+1);
        swap(arr[x][y],arr[X][Y]);
        if(flag)
            return;
    }
}
void init()
{
    ans=-1;
    flag=0;
}
int main()
{
    B[1][1]=2;B[1][2]=2;B[1][3]=2;B[1][4]=2;B[1][5]=2;
    B[2][1]=1;B[2][2]=2;B[2][3]=2;B[2][4]=2;B[2][5]=2;
    B[3][1]=1;B[3][2]=1;B[3][3]=0;B[3][4]=2;B[3][5]=2;
    B[4][1]=1;B[4][2]=1;B[4][3]=1;B[4][4]=1;B[4][5]=2;
    B[5][1]=1;B[5][2]=1;B[5][3]=1;B[5][4]=1;B[5][5]=1;
    cin>>T;
    while(T--)
    {
        init();
        for(int i=1;i<=5;i++)
        {
            for(int j=1;j<=5;j++)
            {
                cin>>ip;
                if(ip=='*')
                {
                    arr[i][j]=0;
                    st1=i;
                    st2=j;
                }
                else
                    if(ip=='0')
                        arr[i][j]=1;
                    else
                        arr[i][j]=2;
            }
        }
        for(limit=Get();limit<=15;limit++)
        {
            IDAstar(st1,st2,0);
            if(ans!=-1)
            {
                cout<<ans<<endl;
                break;
            }
        }
        if(ans==-1)
            cout<<ans<<endl;
    }
}