暇だし作ってみた
http://ideone.com/GQy1O

アルゴリズムは>>563の方法で作った盤面をハッシュテーブルに保存して
最短経路のみを計算するって感じ