RT，有人有什么优化思路吗

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
//#define int long long
#define MAXN 1001
using namespace std;
string s;
int a[10][10],b[10][10]={{0,0,0,0},{0,1,2,3},{0,8,0,4},{0,7,6,5}};//值为i，目标图
int dir[10][10]={{0},{-1,0},{1,0},{0,-1},{0,1}};
struct kx{
	int f[10][10],cnt,x,y,ans;//图，已经移动的距离,0的位置,不在位置上的个数
	bool operator > (const kx & tmp)const{
		return cnt+ans>tmp.ans+tmp.cnt;
	} 
};
kx st;
signed main(){
	ios::sync_with_stdio(false); 
	cin>>s;
	int sx,sy;
	for(int i=0;i<s.size();i++){
		a[i/3+1][i%3+1]=s[i]-'0';
		if(s[i]-'0'==0){
			sx=i/3+1;
			sy=i%3+1;
		}
	}
	st.x=sx;
	st.y=sy;

	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			st.f[i][j]=a[i][j];
		}
	}

	st.cnt=0;

	int ans2=0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(a[i][j]!=b[i][j]) ans2++;
		}
	}
	st.ans=ans2;

	priority_queue<kx,vector<kx>,greater<kx> > q;
	q.push(st);

	while(!q.empty()){
		kx h=q.top();
		q.pop();
		if(h.ans==0){
			cout<<h.cnt;
			break;
		}
		for(int i=1;i<=4;i++){
			int dx=h.x+dir[i][0],dy=h.y+dir[i][1];
			if(dx>=1&&dx<=3&&dy>=1&&dy<=3){
				kx e=h;
				e.cnt++;
				if(e.f[dx][dy]==b[dx][dy]){
					e.ans++;
				}
				if(e.f[e.x][e.y]==b[e.x][e.y]){
					e.ans++;
				}
				if(b[dx][dy]==0){
					e.ans--;
				}
				if(b[e.x][e.y]==e.f[dx][dy]){
					e.ans--;
				}
				swap(e.f[dx][dy],e.f[e.x][e.y]);
				e.x=dx,e.y=dy;
				q.push(e);
			}
		}
	}
	return 0;
}