とある天空都市に住む大学生のGは、芋虫のいも太郎を飼っている。 彼は、いも太郎に最短歩数で全てのえさを順番に食べるように躾けをした。彼の友人であるあなたは、彼からいも太郎が本当に躾けられているかどうかを調べて欲しいと依頼されたので、プログラムを書くことにした。
複数の障害物とエサがグリッド状のエリア内に存在する。頭と 5 つの胴体を持つ芋虫がこのエリアを探索する。芋虫が順番に最後までエサを食べたときの最小の歩数を求めよ。 ただし全てのエサを食べることが不可能な場合は -1 を出力すること。なお、エサの上に芋虫の頭が重なったとき、エサを食べることができる。
エリアは以下の文字で構成される。
芋虫は頭 ’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 番目の元へ‥… というように頭の軌跡をたどるように胴体が動く。以下は、1マス左へ動くときの例である。
移動前 移動後 ...... ...... ...bc. ...cd. ..Sad. .Sabe. ....e. ......
芋虫の移動できる場所は以下のように定められている。
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´ は芋虫の初期状態を表している。初期状態の芋虫に覆われるようにしてエサや障害物は存在しない。また、芋虫の初期位置およびエサの位置は正しく入力されることが保証されている。
芋虫がエサを順番通りに食べたときの最小の歩数、またそれが不可能なら -1 を出力せよ。
5 8 3 #....... #.####2# #.#.3..# #.###### .1Sabcde
14
2 6 2 .1.baS .2.cde
7
2 6 2 .1#baS .2.cde
-1