很明显可以看出是一道搜索题。
首先考虑 \(bfs\)，第一种思路是每次从给定的初始状态都进行一次 \(bfs\)，直到 \(30\) 停止。然后我们发现，初始状态根据一开始空格的位置不同，一共只有 \(9\) 种。而一个状态可以用空格的位置、所有位置上方的颜色、所有位置左方的颜色唯一确定，一共 \(6^8\cdot 9\) 种合法状态。而在目标状态中，我们只有左方不知道，可以先预处理所有初始状态下的所有状态的结果，然后枚举当前状态的左方状态找最小值。
我们发现，这样，预处理部分需要处理 \(6^8\cdot 9\) 次，每次平均需要转移 \(3\) 次，每次转移的同时重新编码的开销是 \(3\cdot 3\)。唯一不会卡满的是 \(30\) 的限制，但其实也大差不差。这样的预处理本地大概需要 \(4\) 秒左右完成，POJ 就不太能过了。
考虑优化，我们发现，四个边和四个角的状态是等价的。我们就可以将所有的询问旋转直到初始的空位在左上角或上方或正中间。这样预处理就只有 \(3\) 次，本地可以 \(2\) 秒以内完成，但是 POJ 依旧过不去。
到这里，我们 \(bfs\) 做法已经优化到极限，需要尝试换一种思路。
考虑 \(dfs\)。在 \(dfs\) 的过程中，我们加入一些优化。首先 \(dfs\) 的天然性质决定了我们可以不必复制状态，直接在原状态基础上改变再推回来，就能进行一次 \(dfs\)，效率远远高于需要每次复制状态继续往下做。其次，\(dfs\) 可以进行剪枝——如果当前剩下需要的步数加上已有的步数已经大于等于已有的答案，就不需要进行下去了。剩下需要的最少步数可以用“当前状态和目标状态不同的位置个数-1”估算。因为很明显我们需要沿着一条路径走。
但是，最重要的一个优化是不走回头路，每次记录当前的状态是从哪里来的。不直接回到自己的祖先。这样的优化是十分可观的，\(3\) 到 \(2\)，\(2\) 到 \(1\)。
同时我们大略估计一下，因为我们不可能每次都在正中间，不走回头路的情况下，卡的最满的也就是每次在角上绕一个圈子，\(4\) 步一共 \(12\) 种，而且根本卡不满，再加上估价函数的优化，就足以通过。
不过在 POJ 的机子上依旧很卡常就是了。
char goal[3][3];
int x,y,ans,dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
struct block{
char u,l,d;
block(){
}
block(char _u,char _l,char _d){
u=_u,l=_l,d=_d;
}
};
block p[3][3];
inline int match(){
int cnt=0;
rd(i,3)rd(j,3)if(p[i][j].u!=goal[i][j])cnt++;
return cnt;
}
inline void dfs(int dep,int x,int y,int X,int Y){
int H=match();
if(!H){
ans=min(ans,dep);
return;
}
if(ans<dep+H||dep>=30)return;
rd(k,4){
int nx=x+dx[k],ny=y+dy[k];
if(nx<0||nx>2||ny<0||ny>2)continue;
if(X==nx&&Y==ny)continue;
swap(p[x][y],p[nx][ny]);
if(k<2)swap(p[x][y].u,p[x][y].d);
else swap(p[x][y].u,p[x][y].l);
dfs(dep+1,nx,ny,x,y);
if(k<2)swap(p[x][y].u,p[x][y].d);
else swap(p[x][y].u,p[x][y].l);
swap(p[x][y],p[nx][ny]);
}
}
inline void solve(){
x--,y--,ans=31;swap(x,y);
rd(i,3)rd(j,3)cin>>goal[i][j];
rd(i,3)rd(j,3){
p[i][j].u='W';
p[i][j].l='B';
p[i][j].d='R';
}p[x][y].u='E';
dfs(0,x,y,-1,-1);
if(ans==31)cout<<-1<<endl;
else cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>x>>y;
while(x){
solve();
cin>>x>>y;
}
return 0;
}//Nyn-siyn-hert