猛新求助简单的DFS

#include <bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int mp[10][10],sx,sy;
int dep;
bool solve;
const int dy[8]={-2,-1,1,2,2,1,-1,-2};
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int check[7][7]={
    {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 f(){
    int diff=0;
    for(int i=1;i<=5;++i)
	for(int j=1;j<=5;++j) if(mp[i][j]!=check[i][j]) diff++;
    return diff;
}
void IDDFS(int now,int x,int y){
    if(solve) return;
    if(now+f()>dep) return;
    if(!f()){
	solve=1;
	return;
    }
    for(int i=0;i<8;++i){
	int xx=x+dx[i],yy=y+dy[i];
	if(xx<1||yy<1||xx>5||yy>5) continue;
	swap(mp[xx][yy],mp[x][y]);
	IDDFS(now+1,xx,yy);
	swap(mp[xx][yy],mp[x][y]);
    }
}
int main(){
    int T=read();
    while(T--){
	for(int i=1;i<=5;++i)
	    for(int j=1;j<=5;++j){
		char c;
		cin>>c;
		if(c=='*') mp[i][j]=2,sx=i,sy=j;
		else mp[i][j]=c-'0';
	    }
	solve=0;
	for(dep=1;dep<=15;++dep){
	    IDDFS(0,sx,sy);
	    if(solve) break;
	}
	if(dep>15) puts("-1");
	else cout<<dep<<endl;
    }
    return 0;
}