Лёгкая дорога
2 ≤ N, M ≤ 100
На сетке размером N на M находится злое существо, и вы хотите уничтожить его с помощью лазерного генератора, расположенного в другой клетке. Поскольку местоположение и направление лазерного генератора фиксированы, вам, возможно, придется использовать несколько зеркал для отражения лазерных лучей. На сетке есть некоторые препятствия, и у вас ограниченное количество зеркал. Определите, возможно ли уничтожить существо, и если да, найдите минимальное количество зеркал, необходимых для этого.
Существует два типа односторонних зеркал: зеркала типа P, которые могут быть установлены под углом 45 или 225 градусов от направления восток-запад, и зеркала типа Q, которые могут быть установлены под углом 135 или 315 градусов. Например, четыре зеркала расположены правильно, и лазер проходит следующим образом.
A
A
0 ≤ A ≤ 10
Обратите внимание, что зеркала односторонние, и поэтому обратная сторона (сторона с крестом на изображении выше) не отражает. У вас есть зеркала типа P и зеркала типа Q. Хотя вы не можете размещать зеркала на клетках с существом или лазерным генератором, лазерный луч может проходить через эти клетки. Злое существо уничтожается, если лазер достигает клетки, в которой оно находится.
Входные данные
Каждый тестовый случай состоит из нескольких строк.
N
M
A
N
M
Первая строка содержит три целых числа: N, M и A. Каждая из следующих строк содержит символы, представляющие информацию о сетке. Символы '#', '.', 'S', 'G' обозначают препятствие, пустую клетку, местоположение лазерного генератора и местоположение злого существа соответственно. Первая строка описывает самые северные клетки, а последняя строка — самые южные. Вы можете предположить, что существует ровно один лазерный генератор и ровно одно существо, и лазерный генератор всегда излучает лазерный луч на юг.
Выходные данные
Выведите минимальное количество использованных зеркал, если вы можете уничтожить существо, или -1, если это невозможно.