Ayı Misha
Ayı Misha kiçik bir xəzinə tapdı - gizlədilmiş bir bal qabı! O, həvəslə bal yeyirdi, amma birdən bir arı onu gördü və həyəcan siqnalı verdi. Misha bilir ki, bundan sonra arılar öz pətəklərindən çıxıb onu tutmaq üçün ətrafa yayılacaqlar. O bilir ki, qabı atıb tez evə getmək lazımdır, amma bal o qədər şirindir ki, Misha onu yeməyi çox erkən dayandırmaq istəmir. Misha'ya bal yeməyi dayandırmaq üçün son mümkün anı müəyyən etməyə kömək edin.
Meşə kvadrat şəbəkə şəklində bir xəritə ilə təmsil olunur, bu şəbəkə n × n ölçüsündə vahid hüceyrələrdən ibarətdir, tərəfləri "şimal-cənub" və "qərb-şərq" istiqamətlərinə paraleldir. Meşənin hər bir hüceyrəsi ya ağac, ya ot, ya pətək, ya da Misha'nın evi ilə doludur. İki hüceyrə qonşu adlanır, əgər biri digərinin birbaşa şimalında, cənubunda, şərqində və ya qərbində yerləşirsə, amma diaqonalda deyil. Misha çevik deyil, ona görə də yalnız qonşu hüceyrəyə keçə bilər. Misha yalnız ot olan hüceyrələrdə hərəkət edə bilər və ağac və ya pətək olan hüceyrələrdə hərəkət edə bilməz. O, həmçinin bir dəqiqədə s hüceyrədən çox hərəkət edə bilməz.
Həyəcan siqnalı verildiyi anda, Misha bal qabını tapdığı ot olan hüceyrədədir və bütün arılar pətəklərin yerləşdiyi hüceyrələrdədir (meşədə bir neçə pətək ola bilər). Bu andan etibarən, hər bir növbəti dəqiqə ərzində aşağıdakı hadisələr bu qaydada baş verir:
Əgər Misha hələ də bal yeyirsə, o, bal yeməyə davam edib-etməyəcəyinə və ya gedəcəyinə qərar verir. Əgər o, bal yeməyə davam edirsə - o, bütün dəqiqə ərzində hərəkət etmir. Əks halda, o, dərhal gedir və yuxarıda təsvir edildiyi kimi meşədə s hüceyrədən çox olmayan məsafədə hərəkət edir. Misha balı özü ilə götürə bilməz və bir dəfə getdikdən sonra artıq onu yeyə bilməz.
Misha bal yeməyi bitirdikdən və ya dəqiqə ərzində hərəkət etdikdən sonra, arılar bir hüceyrə daha yayılır, yalnız ot olan hüceyrələri tuturlar. Daha dəqiq desək, arılar artıq arıların olduğu hər hansı bir hüceyrə ilə qonşu olan bütün ot hüceyrələrinə yayılırlar. Arılar bir hüceyrəyə gəldikdə, onlar orada həmişəlik qalırlar (arılar hərəkət etmir, yayılırlar).
Başqa sözlə, arılar belə yayılır: həyəcan siqnalı verildikdə, arılar pətəklərin yerləşdiyi hüceyrələrdədir. Birinci dəqiqənin sonunda onlar pətəklərlə qonşu olan bütün ot hüceyrələrini tuturlar və pətəklərin yerləşdiyi hüceyrələrdə qalırlar. İkinci dəqiqənin sonunda arılar əlavə olaraq pətəklərlə qonşu olan hüceyrələrlə qonşu olan bütün ot hüceyrələrini tuturlar və s. Kifayət qədər vaxt keçdikdə, arılar çata biləcəkləri bütün ot hüceyrələrini tutacaqlar.
Nə Misha, nə də arılar meşənin sərhədlərini keçə bilməzlər. Həmçinin qeyd edin ki, təsvir olunan qaydalara görə, Misha balı tam dəqiqə ərzində yeyir.
Arılar Misha'yı tuturlar, əgər hər hansı bir anda Misha arılar tərəfindən tutulan bir hüceyrədə olarsa.
Meşə xəritəsinə əsasən, Misha'nın başlanğıc yerində bal yeməyə davam edə biləcəyi maksimum dəqiqə sayını müəyyən edən bir proqram yazın, hələ də arılar onu tutmadan evə qayıda bilmək imkanı ilə.
Giriş verilənləri
Birinci sətir iki tam ədəd - meşə xəritəsinin ölçüsü (tərəfin uzunluğu) n (1 ≤ n ≤ 800) və Misha'nın hər dəqiqədə edə biləcəyi maksimum hərəkət sayı s (1 ≤ s ≤ 1,000), aralarında boşluq ilə ayrılmışdır.
Sonrakı n sətirlər meşə xəritəsini təyin edir. Bu sətirlərin hər biri xəritədə bir hüceyrəni təyin edən n simvolu ehtiva edir. Mümkün simvollar və onların mənaları aşağıda təsvir edilmişdir:
T ağac olan hüceyrəni təyin edir G ot olan hüceyrəni təyin edir M ot olan hüceyrədə Misha'nın başlanğıc yerini və bal qabını təyin edir D Misha'nın girə biləcəyi, amma arıların girə bilmədiyi Misha'nın evinin yerləşdiyi hüceyrəni təyin edir H pətək olan hüceyrəni təyin edir
QEYD: Meşə xəritəsində dəqiq bir M hərfi, dəqiq bir D hərfi və ən azı bir H hərfi olduğu təmin edilir. Həmçinin, Misha'nın başlanğıc yerini və Misha'nın evinin yerləşdiyi hüceyrəni birləşdirən qonşu G hüceyrələrinin ardıcıllığı olduğu təmin edilir, eləcə də pətəklərdən biri ilə Misha'nın başlanğıc yerini birləşdirən qonşu G hüceyrələrinin ardıcıllığı. Ardıcıllıqlar sıfır uzunluğunda ola bilər, əgər Misha'nın evi olan hüceyrə və ya pətək olan hüceyrə Misha'nın başlanğıc yerinə qonşu olarsa. Həmçinin qeyd edin ki, arılar Misha'nın evinin olduğu hüceyrədən keçə bilməzlər. Onlar üçün bu, ağac olan hüceyrə kimidir.
Çıxış verilənləri
Bir tam ədəd - Misha'nın başlanğıc yerində bal yeməyə davam edə biləcəyi maksimum mümkün dəqiqə sayı, təhlükəsiz şəkildə evə qayıda bilmək imkanı ilə.
Əgər Misha arılar onu tutmadan evə qayıda bilməzsə, proqramınız mənfi bir ədəd -1 çıxış etməlidir.