Qala labirintdə#1746
Qala — şahmat fiqurları arasında yer alır və bir gedişdə istənilən sayda hüceyrəni üfüqi və ya şaquli istiqamətdə hərəkət edə bilər. Lakin o, yolunda olan digər fiqurları "aşa bilmir", yəni onların üzərindən keçə bilmir.
Vasya yaxınlarda şahmat taxtasında qeyri-adi bir labirint düzəltdi — taxtanın bəzi hüceyrələrinə piyada (şahmatın ən zəif fiquru) qoydu. İndi isə o, qalanın bir hüceyrədən digərinə ən az neçə gedişə çata biləcəyini bilmək istəyir.
O bu sual üzərində bir neçə gündür düşünür, lakin cavab tapmaq mümkün olmur. Buna görə sizdən kömək istəyir. Vasiyanın məsələsinə cavab verən proqram yazın.
Daxil olan faylın birinci sətrində iki natural ədəd: və (1 \le n, m \le 500) — labirintin ölçüləri verilir.
Sonrakı sətrin hər biri simvoldan ibarətdir. Bu sətrlərin -cisinin -ci simvolu koordinatına malik hüceyrəyə uyğundur. Simvol "." (nöqtə) olarsa, hüceyrə boşdur, P olarsa, piyada yerləşir, S başlayacaq qalanın mövqeyini, F isə son nöqtəni göstərir.
Çıxış faylına qalanın başlanğıc hüceyrədən son hüceyrəyə çata bilməsi üçün tələb olunan minimal gediş sayını çap edin. Əgər son hüceyrə başlanğıc nöqtədən əlçatmazdırsa, -1 çap edin.
Nümunə 1