Задача №114880. Древний замок

Кэл Кестис обнаружил древний храм Силы. Вход в храм находится в прямоугольной пещере. Чтобы попасть в храм, нужно открыть рунический замок, которым запечатан вход.

Пещера, в которой находится вход в храм, имеет размеры \(n \times m\) метров, и поделена на квадраты размера \(1 \times 1\) метр. Представим пещеру в виде таблицы \(n \times m\), строки которой пронумерованы от \(1\) до \(n\) сверху вниз, а столбцы — от \(1\) до \(m\) слева направо. В некоторых квадратах находятся рунические камни, а остальные квадраты свободны. Кэл может перемещаться только по свободным квадратам. За единицу времени он может переместиться из квадрата в соседний по стороне.

Сейчас Кэл находится в некотором квадрате пещеры. Чтобы открыть вход в храм, нужно в правильном порядке коснуться нескольких рунических камней. После чего, Кэл должен дойти до квадрата, в котором откроется вход в храм. Чтобы коснуться рунического камня, расположенного в некотором квадрате, Кэл должен встать в квадрате, соседнем по стороне. На то, чтобы коснуться камня, Кэл не тратит дополнительного времени.

За Кэлом гонятся инквизиторы Империи, и он хочет узнать, за какое минимальное время можно открыть замок и войти в храм. Помогите ему узнать эту величину.

Входные данные

В первой строке даны три целых числа \(n\), \(m\) и \(k\) — размеры пещеры и длина последовательности камней, до которых Кэл должен дотронуться (\(1 \le n, m \le 100\); \(0 \le k \le 100\)).

В следующих \(n\) строках дано по \(m\) символов — описание пещеры. Символ « # » соответствует непроходимой клетке, содержащей камень. Все остальные клетки свободны. Символ « S » соответствует квадрату, в котором Кэл находится изначально. А символ « F » соответствует квадрату, в котором откроется вход в храм. Кэл должен будет прийти в него после того, как откроет замок. Все остальные символы равны « . ». Гарантируется, что символы « S » и « F » встречаются ровно по одному разу.

В следующих \(k\) строках даны по два целых числа \(x_i\) и \(y_i\) — номер строки и столбца, на пересечении которых находится \(i\)-й камень, которого Кэл должен коснуться. Гарантируется, что квадрат на пересечении строки номер \(x_i\) и столбца номер \(y_i\) содержит камень для всех \(i\) от \(1\) до \(k\).

Выходные данные

Если Кэл не сможет открыть замок и войти в храм, выведите число \(-1\). Иначе, выведите минимальное время, необходимое, чтобы открыть замок и дойти до входа в храм.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Ограничения Необходимые подзадачи Информация о проверке
1 11 \(k = 0\) первая ошибка
2 34 \(k \le 5\) 1 первая ошибка
3 55 1, 2 первая ошибка

Примечание

В первом примере, Кэл сначала должен дойти до квадрата \((1, 2)\) за \(8\) шагов. Коснуться камня \((1, 1)\). Перейти в соседний справа квадрат. Коснуться камня \((2, 3)\). Затем, дойти до квадрата \((3, 2)\) за \(7\) шагов. Коснуться камня \((2, 2)\). Перейти в соседний слева квадрат. После чего, его маршрут закончится. Суммарно он потратит \(8 + 1 + 7 + 1 = 17\) единиц времени.

Примеры
Входные данные
3 5 3
#....
####.
FS...
1 1
2 3
2 2
Выходные данные
17
Входные данные
3 5 1
#....
#####
FS...
1 1
Выходные данные
-1
Входные данные
3 5 0
F#...
.#.#.
...#S
Выходные данные
10
Сдать: для сдачи задач необходимо войти в систему