原题链接：https://www.acwing.com/problem/content/4231/
//IDA*
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<queue>
#include<cmath>
using namespace std;
#define x first
#define y second
typedef pair<int,string> PIS;
char op[4]={'d','l','r','u'};
int dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};
int pos[10];//pos记录每一个数字在ed中的下标
int path[101000];
string st,ed;
int f()
{
int res=0;
for(int i=0;i<9;i++)
{
if(st[i]!='X')
{
int a=st[i]-'0';
res+=abs(i/3-pos[a]/3)+abs(i%3-pos[a]%3);
}
}
return res;
}
bool dfs(int k,int depth)
{
if(k+f()>depth) return false;
if(st==ed) return true;
int x1,y1;
for(int i=0;i<9;i++)
if(st[i]=='X') x1=i/3,y1=i%3;
string last=st;
for(int i=0;i<4;i++)
{
int x=dx[i]+x1,y=dy[i]+y1;
//重要剪枝，避免往回走
if(k>=1&&i+path[k-1]==3) continue;
if(x<0||x>=3||y<0||y>=3) continue;
swap(st[x1*3+y1],st[x*3+y]);
path[k]=i;
if(dfs(k+1,depth)) return true;
swap(st[x1*3+y1],st[x*3+y]);
}
return false;
}
int main()
{
int tt;
cin>>tt;
for(int i=1;i<=tt;i++)
{
cin>>st>>ed;
string s=st;
for(int j=0;j<9;j++){
if(ed[j]!='X'){
int a=ed[j]-'0';
pos[a]=j;
}
}
int depth=0;
while(!dfs(0,depth)) depth++;
printf("Case %d: %d\n",i,depth);
for(int i=0;i<depth;i++) cout<<op[path[i]];
cout<<endl;
}
return 0;
}