AT_wupc_06 僕は宇宙人

[problemUrl]: https://atcoder.jp/contests/wupc2nd/tasks/wupc_06 僕は宇宙人．長い旅路の末，遥か彼方からここへやってきたのです．地球はよいところですね． 宇宙人が使うコミュニケーションボードは，$ N $ 行 $ M $ 列のマスから成るボードである．それぞれのマスにはアルファベットが $ 1 $ 文字だけ書かれている．宇宙人は，このボードを次のような決まりで移動することでメッセージの伝達を行う． 1. ボードの任意のマス目の上に乗る． 2. 現在地から，進む方向(左，右，上，下)を1つ決める．初回をのぞき，このときの方向は，直前に進んだ方向とは違うものでなければならない． 3. 決めた方向に，次の伝えたい文字が見つかるまで進む． - このとき，もしもボードの外に出てしまったら，伝達失敗となる． - 移動のとき，進んだマス目に応じたコストがかかる．$ x $ マス進んだときのコストは $ x $ である． 4. 進行中に伝えたい文字が見つかったら，直ちに止まる． 5. 伝えたい文字が残っていない場合は，伝達終了となる．まだ文字が残っている場合は，2. に戻る． このメッセージ伝達手法は，方向の選び方によって伝達に失敗したり，あるいは移動コストがかかりすぎることが問題である． そこで，あなたの仕事はボードの文字と伝えたい文字列が与えられたとき，伝達不可能であるかを判定することと，伝達可能である場合，その最小コストを求めることである． 入力は以下の形式で標準入力から与えられる． > $ 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" と出力せよ． なお、最後には改行を出力せよ． ```

3 3 2
ab
xzz
azb
zzz
```

 ```
3
```

 ```
3 4 2
ab
xzza
azzz
zzbz
```

 ```
-1
```
                            

N/A

N/A