28783번 - Древний замок 다국어

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

Пещера, в которой находится вход в храм, имеет размеры $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, 2)$ за $8$ шагов. Коснуться камня $(1, 1)$. Перейти в соседний справа квадрат. Коснуться камня $(2, 3)$. Затем, дойти до квадрата $(3, 2)$ за $7$ шагов. Коснуться камня $(2, 2)$. Перейти в соседний слева квадрат. После чего, его маршрут закончится. Суммарно он потратит $8 + 1 + 7 + 1 = 17$ единиц времени.