F - 僕は宇宙人 Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

　僕は宇宙人．長い旅路の末，遥か彼方からここへやってきたのです．地球はよいところですね．

問題

　宇宙人が使うコミュニケーションボードは，N 行 M 列のマスから成るボードである．それぞれのマスにはアルファベットが 1 文字だけ書かれている．宇宙人は，このボードを次のような決まりで移動することでメッセージの伝達を行う． 　
    　
  1. ボードの任意のマス目の上に乗る．
    2. 　
  2. 現在地から，進む方向(左，右，上，下)を1つ決める．初回をのぞき，このときの方向は，直前に進んだ方向とは違うものでなければならない．
    3. 　
  3. 決めた方向に，次の伝えたい文字が見つかるまで進む．
      4. 　　　
    • このとき，もしもボードの外に出てしまったら，伝達失敗となる．
      • 　　　
    • 移動のとき，進んだマス目に応じたコストがかかる．x マス進んだときのコストは x である． 　　
    　　
  4. 進行中に伝えたい文字が見つかったら，直ちに止まる．
    5. 　　
  5. 伝えたい文字が残っていない場合は，伝達終了となる．まだ文字が残っている場合は，2. に戻る．
    6. 　
　 このメッセージ伝達手法は，方向の選び方によって伝達に失敗したり，あるいは移動コストがかかりすぎることが問題である．
そこで，あなたの仕事はボードの文字と伝えたい文字列が与えられたとき，伝達不可能であるかを判定することと，伝達可能である場合，その最小コストを求めることである．

入力

入力は以下の形式で標準入力から与えられる． 
N　M　L
S
c_{1,1}c_{1,2} ... c_{1,M}
c_{2,1}c_{2,2} ... c_{2,M}
...
c_{N,1}c_{N,2} ... c_{N,M}
  • 1 行目にボードの大きさを表す N(1 ≦ N ≦ 100) と M(1 ≦ M ≦ 100)，および伝えたい文字列の文字数 L(1 ≦ L ≦ 100) が半角スペース区切りで与えられる．
  • 2 行目にはアルファベットの小文字のみを含む長さ L の文字列 S が与えられる．これは宇宙人が伝えたい文字列を表している．
  • 3 行目～ N+2 行目には，M 文字のアルファベットの小文字のみを含む文字列が与えられる．これらはボードに書かれている文字を表すデータである．

出力

メッセージの伝達に必要な最小コストを 1 行に出力せよ．もし伝達が不可能である場合は，"-1" と出力せよ．
なお、最後には改行を出力せよ．

入力例 1

3 3 2
ab
xzz
azb
zzz

出力例 1

3
最初に 'x' の位置に乗り，'a' まで移動し止まる．その次に右に進み，'b' まで移動し止まる．これにより，最小コスト 3 が達成できる．

入力例 2

3 4 2
ab
xzza
azzz
zzbz

出力例 2

-1
どの場所の 'a' から上下左右の方向に進んでも 'b' には到達できないため，メッセージの伝達は不可能である．