표 위의 편집 거리

표에는 $H$개의 행과 $W$개의 열이 있다. 각 칸에는 알파벳 소문자가 하나씩 적혀 있다.

다음 과정으로 문자열을 만든다.

1. 칸 하나를 고르고, 그 칸의 글자 하나로 이루어진 길이 1의 문자열 $S$를 만든다.
2. 다음 중 하나를 고른다.
   • $S$ 만들기를 멈춘다.
   • 현재 칸과 변을 공유하는 네 칸 중 하나를 고른다. 그 칸의 글자를 $S$의 뒤에 붙이고 그 칸으로 이동한다. 그 뒤에는 2번을 반복한다.

문자열 $T$가 주어진다. 목표는 $S$와 $T$의 편집 거리를 최소화하는 것이다.

두 문자열 $U$와 $V$의 편집 거리는 $U$를 $V$로 바꾸는 데 필요한 연산 횟수의 최솟값이다. 사용할 수 있는 연산은 다음 세 가지다.

• 문자 하나를 다른 문자로 바꾼다.
• 문자 하나를 삽입한다.
• 문자 하나를 삭제한다.

첫 줄에 $H$와 $W$가 주어진다. 이어지는 $H$개의 줄은 표의 각 행을 나타낸다. 마지막 줄에 문자열 $T$가 주어진다. $T$는 비어 있지 않으며 길이는 2000 이하이다. 표의 글자와 $T$는 모두 알파벳 소문자로 이루어진다.

$S$와 $T$의 편집 거리의 최솟값을 한 줄에 출력한다.