这道题可以作为A*的入门题

什么是A*

这是A* 的定义：A*搜索
我的理解是，A*是一种剪枝方式，可以广泛运用于搜索中。
A*的思想是定义一个估值函数，表示最理想的情况下还需要多少步才能达到想要的结果（真实情况所需的步数会大于等于估值函数的返回值），如果当前步数(定义为g(x))+估值函数(定义为h(x))已经超出了前面的最理想情况那么就可以直接结束搜索

本题的估值函数

前面说了，估值函数表示最理想的情况，那对于本题来说，我们只需要计算当前的状态与标准状态有几个不一样，那么最理想的情况下就只需要不一样的点的数目-1步，为什么是-1呢？因为最后一次交换会使得两个点变得和标准一样，所以是-1

int h(){//估值函数
    int value=0;
    for(int i=0;i<5;++i){
        for(int j=0;j<5;++j){
            value+=mp[i][j]!=Ok[i][j];
        }
    } 
    return value;
}

完整代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int go[2][8]={{-1,-1,-2,-2,1,1,2,2},{-2,2,-1,1,2,-2,1,-1}};
int T;
char mp[6][6];
int ans;
char Ok[6][6]={{"11111"},{"01111"},{"00*11"},{"00001"},{"00000"}};
int h(){//估值函数
    int value=0;
    for(int i=0;i<5;++i){
        for(int j=0;j<5;++j){
            value+=mp[i][j]!=Ok[i][j];
        }
    } 
    return value;
}
void swap_(char &a,char &b){
    char c=a;
    a=b;
    b=c;
}
void dfs(int deep,int x,int y){
    int v=h();//至少还需要多少步 
    if(v==0){
        ans=min(deep,ans);
        return;
    }
    if(v+deep>=ans)return;
    for(int i=0;i<8;++i){
        if(x+go[0][i]>=0&&x+go[0][i]<=4&&y+go[1][i]>=0&&y+go[1][i]<=4){
            swap_(mp[x][y],mp[x+go[0][i]][y+go[1][i]]);
            dfs(deep+1,x+go[0][i],y+go[1][i]);
            swap_(mp[x][y],mp[x+go[0][i]][y+go[1][i]]);
        }
    }
}
int main(){
    T=Read();
    while(T--){
        ans=17;
        for(int i=0;i<5;i++)scanf("%s",mp[i]);
        int sx,sy;
        for(int i=0;i<5;++i){
            for(int j=0;j<5;++j){
                if(mp[i][j]=='*'){
                    sx=i;
                    sy=j;
                }
            }
        }
        dfs(0,sx,sy);
        printf("%d\n",ans==17?-1:ans);
    }
    return 0;
}

为什么ans初始值为17？
因为deep表示当前步数，v表示至少需要的步数+1,而这两者相加为17则表示至少要16步，不符合小于等于15的题目要求

以上代码已经足够解决此题，但是如果棋盘再大一点，步数限制再宽一点呢？那就有超时的风险了。
做题时，我们应该尽可能追求完美 ~~（我们学校的校训就是“止于至善”）~~

进一步思考

还有没有优化的办法？
当然有：
我们在前面的搜索过程中可能会存在来回走的情况，我们可以用一个标记来防止这种情况：

int go[2][8]={{-1,-1,-2,-2,1,1,2,2},{-2,2,-1,1,2,-2,1,-1}};//这个表是重点
void dfs(int deep,int x,int y,int pre){
    int v=h();//至少还需要多少步 
    if(v==0){
        ans=min(deep,ans);
        return;
    }
    if(v+deep>=ans)return;
    for(int i=0;i<8;++i){
        if(pre!=-1&&i==(pre+4)%8)continue;
        if(x+go[0][i]>=0&&x+go[0][i]<=4&&y+go[1][i]>=0&&y+go[1][i]<=4){
            swap_(mp[x][y],mp[x+go[0][i]][y+go[1][i]]);
            dfs(deep+1,x+go[0][i],y+go[1][i],i);
            swap_(mp[x][y],mp[x+go[0][i]][y+go[1][i]]);
        }
    }
}

只要我们在打表的时候注意一点，使得每隔4个就是往反方向走的，这样就可以在dfs的时候控制它不来回走

拓展：IDA*

IDA* 的全称是迭代加深搜索+A*剪枝，指每次搜索给一个确定的步数上限，如果超过了，就立刻终止搜索，这个步数上限从1开始，逐渐增加，直到某一一个深度能找到答案为止
迭代加深搜索一般与A* 剪枝一起使用

骑士精神__题解

什么是A*

本题的估值函数

完整代码

进一步思考

拓展：IDA*