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