30375번 - Edit distance on table 다국어

문제

You have a table with $H$ rows and $W$ columns. Each cell of the table contains a letter.

You are going to construct a string by the following steps.

• Step 1: Pick up a cell in the table and let $S$ be a string of length 1ドル$ containing the letter in the cell.
• Step 2: Do either
  • stop building $S,ドル or
  • select a cell from four cells which shares an edge with the current one. Then, append the letter in the cell to $S,ドル and move to the cell. Then, repeat step 2.

You also have a string $T$. Your mission is to minimize the edit distance between $S$ and $T$.

The edit distance (also known as Levenshtein distance) between string $U$ and $V$ is the minimum number of steps required to convert $U$ into $V$ by using the following operations.

• Replace a character in $U$ with another one.
• Insert a character into $U$.
• Delete a character from $U$.

입력

The input consists of a single test case in the following format.

$H$ $W$

$c_{1,1} c_{1,2} \dots c_{1,W}$

$c_{2,1} c_{2,2} \dots c_{2,W}$

$\vdots$

$c_{H,1} c_{H,2} \dots c_{H,W}$

$T$

$H$ and $W$ (2ドル \le H, W \le 100$) represents the height and the width of the table respectively. $c_{i,j}$ (1ドル \le i \le H,ドル 1ドル \le j \le W$) is a character in the cell in the $i$-th row and the $j$-th column. $T$ is a non-empty string. The length of $T$ doesn't exceed 2ドル,000円$. $c_{i,j}$ and $T$ consist of lowercase English letters.

출력

Output the minimum possible edit distance between $S$ and $T$ in one line.

제한

힌트