这道题可以作为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* 剪枝一起使用