← 返回题目列表

AtCoder · wupc_06

F. 我是外星人

中文机器翻译题面 查看原题
 我是外星人。经过漫长的旅程,我从遥远的地方来到这里。地球真是个好地方。

問題

 外星人使用的通信板是,N 行 M 一个由列组成的棋盘。每个格子上都有字母 1 只有文字被写下。外星人通过在这个棋盘上按照如下规则移动来传递消息。  
     
  1. 站在棋盘上的任意格子上。
  2.  
  3. 从当前位置,决定一个前进方向(左、右、上、下)。除了首次之外,这时的方向必须与上次前进的方向不同。
  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',因此消息无法传达。