Problem G: Dice
サイコロ３兄弟は三つ子であり一心同体、３つでひとつとも言ってもよい。三つ子であるため見分けがつかないほど似ている。そんなサイコロ３兄弟はA君のお気に入りのおもちゃだ。A君はいつも３つ１セットでサイコロを転がして遊んでいる。このようにA君が楽しく遊ぶおもちゃだが、実は大きな秘密があった。彼らは実は生きていて、話したり自由に動いたりできるのだ。子ども部屋は r × c の大きさのグリッドで表すことができ、とても大きいものが散乱している。
サイコロ３兄弟は室内を東西南北の４方向へ進行方向に向かって転がりながら移動する。その形ゆえに斜め移動ができないのが、少し気の毒である。進行方向にとても大きいものがある場合、サイコロは進行方向に進むことができない。 サイコロ３兄弟は３つで１セットであるため、一度にひとつのサイコロしか移動することができない。また、サイコロたちはその場で回転するなどという器用な能力は持っていない。
彼らが話したり動いたりしている事実は人間には知られてはいけないというのが「おもちゃのルール」である。このルールを破ったおもちゃはこの世から消滅してしまう。A君が出かけているときに動いたり話したりしているおもちゃたちだが、A君が帰宅して子ども部屋に入ってきたときにもとの位置に戻っていなければならない。A君が帰宅した直後は緊急事態であり、A君が子ども部屋にたどり着く前にあらゆるおもちゃは即座にもとの場所へ戻らなければならない。 A君は床を見下ろすかたちになるため、サイコロの場所と上を向いている数字が正しければ、移動したことに気づくことはない。また、サイコロたちは見分けがつかないほど似ているので、どの収納場所にどのサイコロが向かっても支障はない。
そんなある日、A君のおもちゃ箱の中で最も優秀なプログラマーであるあなたに、与えられたサイコロの位置情報と収納場所から最短何手でサイコロ達が収納場所に戻れるかを計算する任務が与えられた。 サイコロ３兄弟を溺愛しているA君の手からサイコロ３兄弟が消えてしまったら、A君は泣いてしまうので、とても重要な任務である。
Input
入力は以下のフォーマットで与えられる。
r c grid1 . . . gridr
gridi は長さ c の文字列で、1から6までの数字か"."か”x”か”o”からなる。
数字は収納場所かつ、到着時のサイコロの上の値を示している。
“.”は普通の床を示している。
“x”はとてもおおきなものを示している。
“o”はサイコロを示している。
入力は以下の制約を満たす
1 ≤ r,c ≤ 20
初期状態でのサイコロの向きは以下の図に従う。
Output
それぞれの入力に対する、各サイコロがすべて収納できるまでの最短手数を求めよ。
Sample Input 1
3 3 4o. 4o. 4o.
Sample Output 1
３
各サイコロが西方向に移動すればよい。
Sample Input 2
4 4 4o.. .o3. .o.. .5..
Sample Output2
3
1行目のにあるサイコロが西方向
2行目のにあるサイコロが東方向
3行目のにあるサイコロが南方向に移動すればよい。
Sample Input 3
6 10 1xxxxxxxxx o.......o. xxxx.xxxx4 xoxx.xxxx. x....3xx.. x..xxxxx..
Sample Output 3
34