Tobo or not Tobo (UVa Live Archive Africa and the Middle East - Africa and Arab - 2008/2009 Alexandria - Egypt)

UVa Live Archive SPOJ Online Judge

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4361

問題

図のようなパズルがあり、1手ごとにA,B,C,Dのいずれかを90度回転させることが出来る。
ある局面を与えるのでその手が何手で初期状態に戻せるか？y手以内で元に戻せない場合は-1を返せ。
0<=y<=9

解法

前もって初期状態から各局面まで何手で辿りつけるか計算しておけば良い。
SPOJでは間に合わないので両側探索を使った。