20分求条，玄2关

#include<bits/stdc++.h>
using namespace std;
const int maxn=5;
const int dx[]={0,1,1,-1,-1,2,2,-2,-2};
const int dy[]={0,2,-2,2,-2,1,-1,1,-1};
const int X[5][5]={
	{1,1,1,1,1},
	{0,1,1,1,1},
	{0,0,2,1,1},
	{0,0,0,0,1},
	{0,0,0,0,0}
};
struct node{
	int M[maxn][maxn];
	int x,y;//空地的坐标 
	int f;
	/*
	M[i][j]=1 黑色
	M[i][j]=0 白色
	M[i][j]=2 空地 
	*/
	bool operator<(const node&other) const{
		return f>other.f;
	}
	long long toint(){
		long long h=0;
        for(int i=0;i<5;i++){
            for(int j=0;j<5;j++){
                if(i!=x||j!=y){
                    h=h*2+M[i][j];
                }
            }
        }
        h=h*5+x;
        h=h*5+y;
        return h;
	}
	int G(){
		int cnt=0;
		for(int i=0;i<5;i++){
			for(int j=0;j<5;j++){ 
				cnt+=X[i][j]!=M[i][j];
			}
		}
		return cnt;
	}
};
char a[maxn][maxn];
int A_star(node st){
	priority_queue<node>q;
	map<long long,int>vis;
	st.f=st.G();
	q.push(st);
	vis[st.toint()]=0;
	while(!q.empty()){
		node cur=q.top();
		q.pop();
		int xx=cur.x,yy=cur.y;
		int d=vis[cur.toint()];
		if(cur.G()==0){
			return d;
		}
		for(int i=0;i<8;i++){
			int nx=dx[i]+cur.x;
			int ny=dy[i]+cur.y;
			if(nx<0||nx>=5||ny<0||ny>=5){
				continue;
			}
			node nxt=cur;
			swap(nxt.M[xx][yy],nxt.M[nx][ny]);
			nxt.x=nx;
			nxt.y=ny;
			nxt.f=nxt.G()+d+1;
			long long state=nxt.toint();
			if(!vis.count(state)){
				vis[state]=d+1;
				if(nxt.f<=15) q.push(nxt);
			}
		}
	}
	return -1;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		node st;//初试状态 
		for(int i=0;i<5;i++){
			string line;
			cin>>line;
			for(int j=0;j<5;j++){
				if(line[j]=='0'){
					st.M[i][j]=0;
				}
				else if(line[j]=='1'){
					st.M[i][j]=1;
				}
				else{
					st.M[i][j]=2;
					st.x=i;
					st.y=j;
				}
			}
		}
		//cout<<st.x<<" "<<st.y<<endl;
		cout<<A_star(st)<<"\n";
	}
	return 0;
}