@Peoples

Добрый день. Пытаюсь решить хитрую задачку, но зашёл в тупик. Пробовал через Флойда-Уоршелла решать - не получилось. Буду благодарен за подсказку.

Задача:
Часто в ЛКШ в первый день организуют какой-то квест по базе, чтобы школьникам, которые
приехали раньше, не было скучно до официального открытия смены.

Карта базы ЛКШ представляет собой таблицу размера n × m (строки нумеруются от 1 до n
сверху вниз, столбцы — от 1 до m слева направо). Каждой клетке таблицы по условиям квеста
соответствует определенная маленькая латинская буква (от ‘a’ до ‘z’).

Изначально вы получаете задание квеста в клетке (ax, ay) (ax-я сверху строка, ay-й слева столбец). Задача квеста — перемещаясь по базе, собрать строку s длины n. Изначально вам выдается
пустая строка, после чего можно:
• за единицу времени перемещаться между соседними по стороне клетками;
• за нулевое время дописать в конец к своей строке символ, соответствующей текущей клетке.

Посчитайте, за какое минимальное время можно собрать строку s. Обратите внимание, что символы можно дописывать только в конец, поэтому «собирать» их нужно ровно в том порядке, в
котором они следуют в строке s.

Формат входных данных
В первой строке даны два целых числа n и m — количество строк и столбцов на карте базы. Во второй строке даны два целых числа ax и ay — стартовое положение. В следующих n строках задано соответствие клеток базы буквам. Каждая из строк состоит ровно из m строчных английских букв. Буква номер j в i-й из строк соответствует букве, которую можно
«собрать» в клетке (i, j). В последней записана строка s из строчных английских букв — цель квеста.

Формат выходных данных
Выведите единственное число — минимальное время на прохождение квеста.

Примеры
2 26
1 1
abcdefghijklmnopqrstuvwxyz
abtxyzutalkhfdyutxzbzhhawj
nut

Ответ: 17

7 7
4 4
abcdefg
xyzabch
wnopqdi
vmvwrej
ulutsfk
tkjihgl
srqponm
squirrel

Ответ: 17

0

@gunslinger

Реализация указанного алгоритма (Флойда-Уоршелла) есть в boost-е (судя по википедии): https://www.boost.org/doc/libs... graph/doc/

0

@alexu_007

Sorry, всё немного сложнее...

0

@mmi1814

Peoples, у обеих задач одинаковый ответ?

0

@alexu_007

Максимальное значение n и m?

0

@mmi1814

нет, результат

0

@Kuzia domovenok

как в первом ответе получилось 17?

0

@CoderPC

ТС похоже забил

0