Problem H: Caterpillar

とある天空都市に住む大学生のGは、芋虫のいも太郎を飼っている。 彼は、いも太郎に最短歩数で全てのえさを順番に食べるように躾けをした。彼の友人であるあなたは、彼からいも太郎が本当に躾けられているかどうかを調べて欲しいと依頼されたので、プログラムを書くことにした。

Problem

複数の障害物とエサがグリッド状のエリア内に存在する。頭と 5 つの胴体を持つ芋虫がこのエリアを探索する。芋虫が順番に最後までエサを食べたときの最小の歩数を求めよ。 ただし全てのエサを食べることが不可能な場合は -1 を出力すること。なお、エサの上に芋虫の頭が重なったとき、エサを食べることができる。

エリアは以下の文字で構成される。

• 何もないマス -> ‘.’
• 障害物 -> ‘#’
• エサ -> ‘1’, ‘2’, ..., ‘9’
• 芋虫の初期位置 -> é ­ ‘S’, 胴体 ‘a’, ‘b’, ‘c’, ‘d’, ‘e’

芋虫は頭 ’S’ から 5 つの胴体 ‘a’, ‘b’, ‘c’, ‘d’, ‘e’ と 順に上下左右の 4 方向に隣接して、それらが連なって構成される。 例えば、芋虫の構成を表したとき、以下の (1) は正しい芋虫の構成であるが、 (2) や (3) のような構成はありえない。

(1) 正しい
.bc
Sad
..e

(2) eが存在しない
Sab
.dc

(3) "Sab" と "cde" とで芋虫が切断されている
Sab
cde

(1) のような正しい芋虫の構成は、入力で与えられた状態から任意の回数の芋虫の移動の間、一貫して保たれる。 つまり、芋虫の頭が、隣接している 4 つのマスのうちのいずれかの空いているマスに一歩進むと、その後に続いて 1 番目の胴体は頭が元あったマスへ動き、2 番目の胴体は 1 番目の胴体が元あったマスへ、 3 番目は 2 番目の元へ‥… というように頭の軌跡をたどるように胴体が動く。以下は、１マス左へ動くときの例である。

移動前    移動後
......   ......
...bc.   ...cd.
..Sad.   .Sabe.
....e.   ......

芋虫の移動できる場所は以下のように定められている。

• 芋虫は自分の胴体、障害物、エリア外を移動することは出来ない。ただしエサの上を、そのエサを食べずに移動することは出来る。
• 移動前に胴体が進む先にあった場合でも、移動後に頭と胴体が重ならないならば移動できる。

Input

H W N
area

入力は H + 1 行で与えられる。1行目には 3つの整数 H, W, N (2 ≤ H ≤ 10, 2 ≤ W ≤ 10, 1 ≤ N ≤ 9) が書かれている。Hはエリアの高さ、Wは幅、Nがエサの個数を表す ( このとき 6 + N ≤ H × W が必ず成立する ) 。

2 行目から H + 1 行目までの各行には ´S´,´1´, 2´ , … ´9´,´a´,´b´,´c´,´d´,´e´,´#´,´.´ からなる W 文字の文字列が書かれており，各々がエリアの各区画の状態を表している。また ´S´,´a´,´b´,´c´,´d´,´e´ は芋虫の初期状態を表している。初期状態の芋虫に覆われるようにしてエサや障害物は存在しない。また、芋虫の初期位置およびエサの位置は正しく入力されることが保証されている。

Output

芋虫がエサを順番通りに食べたときの最小の歩数、またそれが不可能なら -1 を出力せよ。

Sample Input1

5 8 3
#.......
#.####2#
#.#.3..#
#.######
.1Sabcde

Sample Output1

14

Sample Input2

2 6 2
.1.baS
.2.cde

Sample Output2

7

Sample Input3

2 6 2
.1#baS
.2.cde

Sample Output3

-1