刚学搜索优化，自己的代码和题解的代码有一点不同，但是都可以通过测试。

我的

#include<bits/stdc++.h>
using namespace std;
int goal[6][6] = {
{0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1},
{0, 0, 1, 1, 1, 1},
{0, 0, 0, -1, 1, 1},
{0, 0, 0, 0, 0, 1},
{0, 0, 0, 0, 0, 0}};
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[8] = {2, 1, -1, -2, 2, 1, -1, -2}, a[6][6], ID;
int check(int x, int y)
{
	if(x < 1 || x > 5 || y < 1 || y > 5)
	{
		return 0;
	}
	return 1;
}
int g()
{
	int ret = 0;
	for(int i = 1; i <= 5; i++)
	{
		for(int j = 1; j <= 5; j++)
		{
			if(a[i][j] == -1)
			{
				continue;
			}
			if(a[i][j] != goal[i][j])
			{
				ret++;
			}
		}
	}
	return ret;
}
int IDAstar(int dep, int x, int y, int pre)
{
	if(g() == 0)
	{
		return 1;
	}
	if(dep == ID)
	{
		return 0;
	}
	if(dep + g() > ID)
	{
		return 0;
	}
	for(int i = 0; i <= 7; i++)
	{
		int xx = x + dx[i], yy = y + dy[i];
		if(check(xx, yy) && (i + pre != 7))
		{
			swap(a[x][y], a[xx][yy]);
			if(g() + dep <= ID)
			{
				if(IDAstar(dep + 1, xx, yy, i))
				{
					return 1;
				}
			}
			swap(a[x][y], a[xx][yy]);
		}
	}
	return 0;
}
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0);
	int x, y, T;
	cin >> T;
	while(T--)
	{
		ID = 0;
		memset(a, 0, sizeof(a));
		int ret = -1;
		for(int i = 1; i <= 5; i++)
		{
			for(int j = 1; j <= 5; j++)
			{
				char xx;
				cin >> xx;
				if(xx == '*')
				{
					a[i][j] = -1;
					x = i;
					y = j;
					continue;
				}
				a[i][j] = xx - '0';
			}
		}
		for(ID; ID <= 15; ID++)
		{
			if(IDAstar(0, x, y, -1))
			{
				ret = ID;
				break;
			}
		}
		cout << ret << endl;
	}
	return 0;
}

题解

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

int n;
int ans[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 nxtx[]={1,1,2,2,-2,-2,-1,-1};
int nxty[]={2,-2,1,-1,1,-1,2,-2};
int a[10][10],k;
int judge;

int check()
{
    for(int i=1;i<=5;++i)
    for(int j=1;j<=5;++j)
    if(ans[i][j]!=a[i][j])return 0;
    return 1;
}

int test(int step)
{
    int cnt=0;
    for(int i=1;i<=5;++i)
    for(int j=1;j<=5;++j)
    if(ans[i][j]!=a[i][j]){ if(++cnt+step>k) return 0;}
    return 1;
}

void A_star(int step,int x,int y,int pre)//pre记录上一步怎么到当前状态
{
    if(step==k){ if(check())judge=1; return;}
    if(judge) return;
    for(int i=0;i<8;++i)
    {
        int nx=x+nxtx[i],ny=y+nxty[i];
        if(nx<1||nx>5||ny<1||ny>5||i+pre==7) continue;//加入了上述的最优性剪枝
        swap(a[x][y],a[nx][ny]);
        if(test(step)&&!judge) A_star(step+1,nx,ny,i);//A*估价再向下搜索
        swap(a[x][y],a[nx][ny]);
    }
}

int main()
{
    n=read();
    while(n--)
    {
        int x,y; judge=0;
        for(int i=1;i<=5;++i)
        {
            char ss[7]; scanf("%s",&ss);
            for(int j=0;j<5;++j)
            if(ss[j]=='*') a[i][j+1]=2,x=i,y=j+1;
            else a[i][j+1]=ss[j]-'0';
        }
        for(k=1;k<=15;++k)
        {
            A_star(0,x,y,-1);
            if(judge) { printf("%d\n",k); break;}
        }
        if(!judge)printf("-1\n");
    }
    return 0;
}
//niiick

估价函数我是忽略了空位的，但是题解没有忽略。

我的

int g()
{
	int ret = 0;
	for(int i = 1; i <= 5; i++)
	{
		for(int j = 1; j <= 5; j++)
		{
			if(a[i][j] == -1)
			{
				continue;
			}
			if(a[i][j] != goal[i][j])
			{
				ret++;
			}
		}
	}
	return ret;
}

题解

int test(int step)
{
    int cnt=0;
    for(int i=1;i<=5;++i)
    for(int j=1;j<=5;++j)
    if(ans[i][j]!=a[i][j]){ if(++cnt+step>k) return 0;}
    return 1;
}

经测试，如果我的代码中估价函数也忽略空格会导致错误。

求dalao释疑

谢谢！