Yüngül Yol
2 ≤ N, M ≤ 100
N x M ölçülü bir şəbəkədə pis bir məxluq var və siz onu başqa bir kvadratda yerləşən lazer generatoru ilə məhv etmək istəyirsiniz. Lazer generatorunun yeri və istiqaməti sabitdir, buna görə də lazer şüalarını əks etdirmək üçün bir neçə güzgüdən istifadə etməli ola bilərsiniz. Şəbəkədə bəzi maneələr mövcuddur və güzgülərin sayı məhduddur. Məxluqu öldürməyin mümkün olub-olmadığını və mümkündürsə, minimum güzgü sayını tapın.
İki növ tək tərəfli güzgü var: P tipli güzgülər şərq-qərb istiqamətindən 45 və ya 225 dərəcə bucaq altında yerləşdirilə bilər, Q tipli güzgülər isə 135 və ya 315 dərəcə bucaq altında yerləşdirilə bilər. Məsələn, dörd güzgü düzgün yerləşdirildikdə, lazer aşağıdakı kimi keçir.
A
A
0 ≤ A ≤ 10
Qeyd edək ki, güzgülər tək tərəflidir və buna görə də yuxarıdakı şəkildəki çarpaz tərəf (arxa tərəf) əks etdirici deyil. Sizdə həm P tipli, həm də Q tipli güzgülər var. Güzgüləri məxluq və ya lazer generatorunun olduğu kvadratlara qoya bilməsəniz də, lazer şüası kvadratın içindən keçə bilər. Əgər lazer məxluqun olduğu kvadrata çatarsa, pis məxluq öldürülür.
Giriş verilənləri
Hər bir test halı bir neçə sətirdən ibarətdir.
N
M
A
N
M
Birinci sətir üç tam ədəd, , , və . Sonrakı sətirlərdən hər biri simvolları ehtiva edir və şəbəkə məlumatını təmsil edir. '#', '.', 'S', 'G' maneə, boş kvadrat, lazer generatorunun yeri və pis məxluqun yerini göstərir. Birinci sətir ən şimaldakı kvadratların məlumatını, sonuncu sətir isə ən cənubdakı kvadratların məlumatını göstərir. Dəqiq bir lazer generatoru və dəqiq bir məxluq olduğunu və lazer generatorunun həmişə cənuba doğru lazer şüası yaydığını fərz edə bilərsiniz.
Çıxış verilənləri
Əgər məxluqu öldürə bilsəniz, istifadə olunan minimum güzgü sayını, əks halda -1 çıxış edin.