RT，有详细注释，谢谢大佬

#include<bits/stdc++.h>
using namespace std;
const int MAX=10;

int t,a[MAX][MAX]/*当前状态*/;
int sx,sy,flag;
int g[MAX][MAX]= /*目标状态*/
{0,0,0,0,0,0,
 0,2,2,2,2,2,		
 0,1,2,2,2,2,
 0,1,1,3,2,2,
 0,1,1,1,1,2,
 0,1,1,1,1,1,};//1-白 2-黑 3-空格
int dx[9]={0,1,1,-1,-1,2,2,-2,-2},dy[9]={0,2,-2,2,-2,1,-1,1,-1};//移动的方法 

int h(){
	int sum=0;
	for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			if(a[i][j]!=g[i][j])
				sum++;
		}
	}
	
	return sum;
}
int pd(int x,int y){
	return (x<=5&&x>=1&&y<=5&&y>=1);
}
void dfs(int x,int y,int sum,int maxs){//目前的x 目前的y 目前走的层数 最大层数
//	test(maxs);
	if(flag) return ;//找到答案立刻返回 
	if(sum==maxs){
		if(!h())
			flag=1;
		return ;
	} 
	
	for(int i=1;i<=8;i++){//爆搜 
		int gx=x+dx[i],gy=y+dy[i];
		if(!pd(gx,gy)) continue;
		swap(a[x][y],a[gx][gy]);
		if(sum+h()<=maxs){//估价函数，可行性剪枝
			dfs(gx,gy,sum+1,maxs);
			if(flag) return ;
		}
		
		swap(a[x][y],a[gx][gy]);//回溯 
	}
}
int main(){
//	freopen("IDA*.in","r",stdin);
//	freopen("IDA*.out","w",stdout);
	scanf("%d",&t);
	char ch;
	while(t--){
		for(int i=1;i<=5;i++){//读入数据 
			for(int j=1;j<=5;j++){
				ch=getchar();
				while(ch!='1'&&ch!='0'&&ch!='*')
					ch=getchar();
				if(ch=='*')
					a[i][j]=3,sx=i,sy=j;
				else
					a[i][j]=ch-'0'+1;
			}
		}
		
		if(!h()){printf("0\n"); continue;}//特判是否就是目标状态
		for(int i=1;i<=15;i++){//枚举搜索层数
			dfs(sx,sy,0,i); 
			if(flag){printf("%d\n",i); break;}
		} 
		
		if(!flag) printf("-1\n");
		flag=0;
	}

	return 0;
}