Dice

Time Limit : 6 sec, Memory Limit : 262144 KB

Problem G: Dice

サイコロ3兄弟は三つ子であり一心同体、3つでひとつとも言ってもよい。三つ子であるため見分けがつかないほど似ている。そんなサイコロ3兄弟はA君のお気に入りのおもちゃだ。A君はいつも3つ1セットでサイコロを転がして遊んでいる。このようにA君が楽しく遊ぶおもちゃだが、実は大きな秘密があった。彼らは実は生きていて、話したり自由に動いたりできるのだ。子ども部屋は r × c の大きさのグリッドで表すことができ、とても大きいものが散乱している。

サイコロ3兄弟は室内を東西南北の4方向へ進行方向に向かって転がりながら移動する。その形ゆえに斜め移動ができないのが、少し気の毒である。進行方向にとても大きいものがある場合、サイコロは進行方向に進むことができない。 サイコロ3兄弟は3つで1セットであるため、一度にひとつのサイコロしか移動することができない。また、サイコロたちはその場で回転するなどという器用な能力は持っていない。

彼らが話したり動いたりしている事実は人間には知られてはいけないというのが「おもちゃのルール」である。このルールを破ったおもちゃはこの世から消滅してしまう。A君が出かけているときに動いたり話したりしているおもちゃたちだが、A君が帰宅して子ども部屋に入ってきたときにもとの位置に戻っていなければならない。A君が帰宅した直後は緊急事態であり、A君が子ども部屋にたどり着く前にあらゆるおもちゃは即座にもとの場所へ戻らなければならない。 A君は床を見下ろすかたちになるため、サイコロの場所と上を向いている数字が正しければ、移動したことに気づくことはない。また、サイコロたちは見分けがつかないほど似ているので、どの収納場所にどのサイコロが向かっても支障はない。

そんなある日、A君のおもちゃ箱の中で最も優秀なプログラマーであるあなたに、与えられたサイコロの位置情報と収納場所から最短何手でサイコロ達が収納場所に戻れるかを計算する任務が与えられた。 サイコロ3兄弟を溺愛しているA君の手からサイコロ3兄弟が消えてしまったら、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

Source: Aizu Competitive Programming Camp 2012 , Day 2, Aizu-Wakamatsu, Japan, 2012-09-04
Problem Setter:  Tomoya Sakai, Kyugo Katsuta, Kazuki Yamamoto