| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 37 | 11 | 8 | 36.364% |
Белка Скрэт постарел и набрался мудрости. Вместо того, чтобы гоняться за тем самым орехом, теперь он хочет собрать коллекцию из орехов разных видов. Всего есть 26ドル$ различных видов орехов, обозначенных символами от 'a' до 'z'. А идеальная коллекция, которую хочет собрать Скрэт, описывается строкой $s,ドル $i$-й символ которой обозначает вид $i$-го ореха в коллекции.
Материк, на котором сейчас находится Скрэт, можно представить как прямоугольное поле размера $n \times m$. Пронумеруем строки поля от 1ドル$ до $n$ сверху вниз, а столбцы поля от 1ドル$ до $m$ слева направо. Клетка $(x, y)$ находится на пересечении строки номер $x$ и столбца номер $y$. Изначально Скрэт находится в клетке $(s_x, s_y)$. В клетке с координатами $(i, j)$ можно найти только орехи вида $x_{i, j},ドル но в бесконечно большом количестве. Рельеф материка устроен так, что перемещение возможно только между соседними по стороне клетками и занимает ровно единицу времени.
Скрэт очень принципиальный, поэтому будет собирать орехи именно в том порядке, в котором они заданы строкой $s$ (иными словами, если $s = \text{<<ab>>},ドル то нельзя сначала подобрать орех вида 'b', а затем орех вида 'a'). Помогите ему определить, за какое минимальное время он может собрать всю коллекцию. На то, чтобы подобрать орех в той клетке, в которой сейчас находится Скрэт, время не тратится.
В первой строке даны два целых числа $n$ и $m$ --- размеры материка (1ドル \le n, m \le 300$). Во второй строке даны два целых числа $s_x$ и $s_y$ --- координаты клетки, в которой Скрэт находится изначально (1ドル \le s_x \le n,ドル 1ドル \le s_y \le m$).
Каждая из следующих $n$ строк состоит ровно из $m$ строчных английских букв. В $i$-й из этих строк $j$-й символ задает $x_{i, j}$ --- вид орехов, растущих в клетке материка $(i, j)$. Гарантируется, что каждый вид орехов присутствует хотя бы в одной клетке материка.
В следующей строке дана строка $s$ из строчных английских букв, задающая последовательность видов орехов в идеальной коллекции (1ドル \le |s| \le 300$).
Выведите единственное число --- минимальное время, которое потребуется Скрэту, чтобы собрать свою коллекцию.
2 26 1 1 abcdefghijklmnopqrstuvwxyz abtxyzutalkhfdyutxzbzhhawj nut
17
7 7 4 4 abcdefg xyzabch wnopqdi vmvwrej ulutsfk tkjihgl srqponm squirrel
17
В первом примере оптимальный маршрут --- дойти до 'n' в первой строке за 12ドル$ шагов, затем спуститься вниз на 1ドル$ и добавить 'u' и 't', стоящие подряд справа, что потребует еще 4ドル$ шага.
Во втором примере оптимальный маршрут задается точками $(4, 4),ドル 's'$(5, 5),ドル 'q'$(3, 5),ドル 'u'$(5, 3),ドル 'i'$(6, 4),ドル 'r'$(4, 5)$ (дважды), 'e'$(4, 6)$ и 'l'$(6, 7)$.