D - Text Input on a Smart TV Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、スマートテレビのリモコンを使って文字列を入力しようとしています。

テレビ画面には H 行 W 列のマス目で構成された文字入力パネルが表示されています。

上から i 行目、左から j 列目のマスを (i, j) とし、そこに書かれた文字を G_{i,j} とします。

カーソルは最初、マス (R, C) の上にあります。

高橋君は、長さ N の文字列 S の 1 文字目、2 文字目、\ldots、N 文字目をこの順に入力したいです。

S のうちまだ入力されていない最も先頭の文字を「次に入力すべき文字」と呼ぶことにします。

高橋君ができる操作は次の 2 種類であり、いずれも 1 回あたりのコストは 1 です。

  • 移動: カーソルがマス (i, j) にあるとき、上下左右に隣接するマスのいずれか 1 つへカーソルを移動する。ただし、パネルの外に出る移動はできない。すなわち、(i-1, j), (i+1, j), (i, j-1), (i, j+1) のうちパネル内にあるマスへのみ移動できる。
  • 決定: 今カーソルがあるマスに書かれた文字が、次に入力すべき文字と一致するときのみ実行できる。その文字を入力し、次に入力すべき文字は S の 1 つ後の文字に進む。決定操作の後もカーソルの位置は変わらない。

同じ文字がパネル上の複数のマスに書かれている場合は、そのどれで決定操作を行っても構いません。また、同じマスで何度でも決定操作を行うことができます。

S のすべての文字を入力し終えた時点で操作は完了です。

高橋君が文字列 S をすべて入力するために必要な操作回数の最小値を求めてください。

S に含まれるいずれかの文字がパネル上に 1 つも存在しない場合、S をすべて入力することは不可能です。この場合は -1 を出力してください。

制約

  • 1 \leq H \leq 100
  • 1 \leq W \leq 100
  • 1 \leq R \leq H
  • 1 \leq C \leq W
  • 1 \leq N \leq 2 \times 10^5
  • H \times W \times N \leq 2 \times 10^6
  • G_{i,j} は英小文字（a 〜 z）である
  • S は英小文字（a 〜 z）からなる長さ N の文字列である
  • H, W, R, C, N は整数である

入力

H W
R C
G_1
G_2
\vdots
G_H
N
S
  • 1 行目には、文字入力パネルの行数を表す H と列数を表す W が、スペース区切りで与えられる。
  • 2 行目には、カーソルの初期位置の行番号 R と列番号 C が、スペース区切りで与えられる。
  • 3 行目から H + 2 行目までの H 行では、文字入力パネルの各行を表す文字列が与えられる。
  • 2 + i 行目では、パネルの i 行目を表す長さ W の文字列 G_i が与えられる。
  • G_i の j 文字目が、マス (i, j) に書かれた文字 G_{i,j} を表す。
  • H + 3 行目には、入力したい文字列の長さを表す N が与えられる。
  • H + 4 行目には、入力したい文字列 S が与えられる。

出力

文字列 S をすべて入力するために必要な操作回数の最小値を 1 行で出力せよ。

入力できない場合は -1 を出力せよ。

入力例 1

3 3
2 2
abc
def
ghi
5
bedhi

出力例 1

11

入力例 2

2 3
1 1
abc
def
2
az

出力例 2

-1

入力例 3

5 6
3 4
abcdef
ghijkl
mnopqr
stuvwx
yzabcd
22
algorithmicprogramming

出力例 3

90

入力例 4

20 30
10 15
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
260
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz

出力例 4

749

入力例 5

1 1
1 1
a
1
a

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is trying to input a string using a smart TV remote control.

The TV screen displays a text input panel consisting of a grid with H rows and W columns.

Let (i, j) denote the cell in the i-th row from the top and j-th column from the left, and let G_{i,j} be the character written in that cell.

The cursor is initially on cell (R, C).

Takahashi wants to input the 1st, 2nd, \ldots, N-th characters of a string S of length N, in this order.

We call the earliest character in S that has not yet been input the "next character to input."

Takahashi can perform the following two types of operations, each with a cost of 1 per execution:

  • Move: When the cursor is on cell (i, j), move the cursor to one of the adjacent cells (up, down, left, or right). However, the cursor cannot move outside the panel. That is, the cursor can only move to a cell among (i-1, j), (i+1, j), (i, j-1), (i, j+1) that is within the panel.
  • Confirm: This can only be performed when the character written on the cell where the cursor currently is matches the next character to input. That character is input, and the next character to input advances to the next character in S. The cursor position does not change after a confirm operation.

If the same character appears in multiple cells on the panel, the confirm operation may be performed at any of them. Also, the confirm operation can be performed at the same cell any number of times.

The process is complete when all characters of S have been input.

Find the minimum number of operations required for Takahashi to input the entire string S.

If any character contained in S does not exist anywhere on the panel, it is impossible to input all of S. In this case, output -1.

Constraints

  • 1 \leq H \leq 100
  • 1 \leq W \leq 100
  • 1 \leq R \leq H
  • 1 \leq C \leq W
  • 1 \leq N \leq 2 \times 10^5
  • H \times W \times N \leq 2 \times 10^6
  • G_{i,j} is a lowercase English letter (a to z)
  • S is a string of length N consisting of lowercase English letters (a to z)
  • H, W, R, C, N are integers

Input

H W
R C
G_1
G_2
\vdots
G_H
N
S
  • The first line gives H, the number of rows of the text input panel, and W, the number of columns, separated by a space.
  • The second line gives R, the row number of the cursor's initial position, and C, the column number, separated by a space.
  • The next H lines (from the 3rd line to the (H+2)-th line) give the strings representing each row of the text input panel.
  • The (2+i)-th line gives a string G_i of length W representing the i-th row of the panel.
  • The j-th character of G_i represents the character G_{i,j} written in cell (i, j).
  • The (H+3)-th line gives N, the length of the string to input.
  • The (H+4)-th line gives S, the string to input.

Output

Output in one line the minimum number of operations required to input the entire string S.

If it is impossible to input, output -1.

Sample Input 1

3 3
2 2
abc
def
ghi
5
bedhi

Sample Output 1

11

Sample Input 2

2 3
1 1
abc
def
2
az

Sample Output 2

-1

Sample Input 3

5 6
3 4
abcdef
ghijkl
mnopqr
stuvwx
yzabcd
22
algorithmicprogramming

Sample Output 3

90

Sample Input 4

20 30
10 15
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
abcdefghijklmnopqrstuvwxyzabcd
260
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz

Sample Output 4

749

Sample Input 5

1 1
1 1
a
1
a

Sample Output 5

1