第2回早稲田大学プログラミングコンテスト

F - 僕は宇宙人


Time limit時間制限 : 3sec / Memory limitメモリ制限 : 256MB

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

問題

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

入力

入力は以下の形式で標準入力から与えられる.
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' には到達できないため,メッセージの伝達は不可能である.

Submit提出する