问题分析

• 状态表示：9个格子的位置排列（共9! = $362880$种状态），每个状态唯一标识九宫格的布局。
• 预处理思想：以初始基准状态（$1-9$按行优先排列，记为$S$）为起点，通过$BFS$计算所有状态到$S$的最短步数。每次查询时，将输入的初始和目标状态映射为相对于$S$的排列（即找到目标状态在$BFS$预处理中的对应状态），直接返回预处理好的距离。 注意 每次 $BFS$ 会超时，所以需要预处理 + 高效查询

解题步骤

1. BFS预处理：
   初始状态：$123456789$（行优先排列），距离为$0$。 生成操作：对当前状态应用$7$种操作（行右移$3$种、列下移$3$种、旋转$1$种），生成新状态。 距离更新：若新状态未访问（$ans$中无记录），记录距离（当前距离$+1$）并入队。

2.查询处理：
映射初始状态：将输入的初始数字映射到基准状态（如初始的$1$对应位置$0$，$2$对应位置1，…，$9$对应位置$8$）。 生成目标状态：根据目标数字的位置，生成目标字符串（如目标中数字$x$的位置对应基准中的位置，转换为字符串）。 查表输出：直接查询预处理好的$ans$，得到最短步数。

复杂度

预处理：$O(9!×7)$ ≈ $2.5e6$，可快速完成。
查询：O(T)，每次查询$O(1)$，适合大规模输入$（T≤2e5）$。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N=1e6+5;
map<string,int>ans;
queue<string>q;
string youyi(string a,int op)//右移函数 
{
	if(op==1)
	{
		char t=a[0];
		a[0]=a[2],a[2]=a[1],a[1]=t;
		return a;
	}
	if(op==2)
	{
		char t=a[3];
		a[3]=a[5],a[5]=a[4],a[4]=t;
		return a;
	}
	if(op==3)
	{
		char t=a[6];
		a[6]=a[8],a[8]=a[7],a[7]=t;
		return a;
	}
}
string xiayi(string a,int op)//下移函数 
{
	if(op==1)
	{
		char t=a[0];
		a[0]=a[6],a[6]=a[3],a[3]=t;
		return a;
	 } 
	 if(op==2)
	 {
	 	char t=a[1];
	 	a[1]=a[7],a[7]=a[4],a[4]=t;
	 	return a;
	 }
	 if(op==3)
	 {
	 	char t=a[2];
	 	a[2]=a[8],a[8]=a[5],a[5]=t;
	 	return a;
	 }
} 
string xuanzhuan(string a)//顺时针旋转函数 
{
	char t=a[0];
	a[0]=a[6],a[6]=a[8],a[8]=a[2],a[2]=t;
 	t=a[1];
 	a[1]=a[3],a[3]=a[7],a[7]=a[5],a[5]=t;
 	return a;
}
void bfs()
{
	q.push("123456789");
	ans["123456789"]=0;
	while(q.size())
	{
		string g=q.front();
		q.pop();
		string t;
		t=youyi(g,1);
		if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
		t=youyi(g,2);
		if(ans[t]==0 )q.push(t),ans[t]=ans[g]+1;
		t=youyi(g,3);
		if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
		t=xiayi(g,1);
		if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
		t=xiayi(g,2);
		if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
		t=xiayi(g,3);
		if(ans[t]==0) q.push(t),ans[t]=ans[g]+1;
		t=xuanzhuan(g);
		if(ans[t]==0) q.push(t),ans[t]=ans[g]+1; 
	}
}
void solve()
{
    string s;
    map<char,char>mp;
    for(int i=1;i<=9;i++)
    {
    	char ch;
    	cin>>ch;
    	mp[ch]='0'+i;
	}
	for(int i=1;i<=9;i++)
	{
		char ch;
		cin>>ch;
		s+=mp[ch];
	}
	if(s=="123456789")cout<<"0"<<endl;
	else if(ans[s]==0)cout<<-1<<endl;
	else cout<<ans[s]<<endl;
}
signed main()
{
	IOS;
	bfs(); 
	int _=1;
	cin>>_;
	while(_--)solve(); 
	return 0;
}