Sehrbazın Ponçiki
Sahibiniz bir günlük şəhərə gedib. Onun danlağını eşitmədən rahat bir gün keçirə bilərsiniz. Amma o, sizə axşama qədər ponçik xəmiri hazırlamağı tapşırıb. Ponçikləri o qədər çox sevir ki, hər gün onlarla ponçik yemədən yaşaya bilmir. Belə gözəl bir gün üçün nə qədər yorucu bir iş.
Amma keçən həftə, sahibinizin istifadə etdiyi sehrli bir tılsımı eşitdiniz. İndi onu sınamağın vaxtı idi. Mətbəxin küncündə oturan süpürgəyə tılsımı oxudunuz. İşıqların parıltısı ilə süpürgə iki qol və iki ayaq çıxardı və canlandı. Ona əmr etdiniz, o da anbarı gətirdi və xəmir yoğurmağa başladı. Tılsım işlədi və necə də sürətlə yoğurdu!
Bir neçə dəqiqə sonra, mətbəx masasında hündür bir xəmir yığını vardı. Bu, növbəti həftə üçün kifayət idi. "Tamam, indi dayan," dediniz. Amma o dayanmadı. Kömək edin! Onu dayandırmaq üçün tılsımı bilmirdiniz! Tezliklə mətbəx masası yüzlərlə xəmir parçası ilə doldu və o, hələ də bacardığı qədər sürətlə işləyirdi. İndi onu dayandıra bilməsəniz, xəmir parçaları ilə dolu mətbəxdə boğulacaqsınız.
Gözləyin, sahibiniz tılsımlarını dəftərlərinə yazmırdı? Onun otağına getdiniz və dayandırma tılsımını qeyd etdiyi dəftəri tapdınız.
Amma bu hekayənin sonu deyildi. Dəftərdə yazılan tılsım başqaları tərəfindən asanlıqla oxunmurdu. O, tılsımı qeyd etmək üçün ponçik şəklində plastik bir modeldən istifadə etmişdi. Ponçik şəklindəki modelin səthini kvadrat tor şəklində bölmüş (Şəkil 1) və hərflərlə doldurmuşdu (Şəkil 2). Tılsımı o qədər diqqətlə gizlətmişdi ki, səthdəki naxış mənasız görünürdü. Amma siz bilirdiniz ki, o, naxışı elə yazmışdı ki, tılsım bir neçə dəfə "görünsün" (dəqiq şərtlər üçün növbəti paraqrafa baxın). Tılsım mütləq soldan sağa istiqamətində yazılmamışdı, amma 8 istiqamətdən hər hansı birində, yəni soldan sağa, sağdan sola, yuxarıdan aşağıya, aşağıdan yuxarıya və 4 diaqonal istiqamətdə ola bilərdi.
Tılsımı bir neçə dəfə görünən ən uzun sətir kimi tapmalısınız. Burada, bir sətir, ponçik üzərindəki kvadrat ardıcıllıqların aşağıdakı şərtləri təmin etməsi halında bir neçə dəfə görünmüş sayılır.
Hər bir kvadrat ardıcıllıq öz-özünü üst-üstə düşməz. (İki kvadrat ardıcıllıq bəzi kvadratları paylaşa bilər.)
Kvadrat ardıcıllıqlar fərqli kvadratlardan başlayır və/və ya fərqli istiqamətlərə gedir.
Qeyd edək ki, bir palindrom (yəni, geri və ya irəli oxuduğunuzda eyni olan bir sətir) birinci şərti təmin edərsə, iki dəfə "görünür". Ponçik üzərindəki naxış hərflər matrisi kimi verilir.
ABCDEFGHIJKL
Qeyd edək ki, ponçikin səthinin sonu yoxdur; naxışın yuxarı və aşağı tərəfləri, həmçinin sol və sağ tərəfləri bir-birinə bağlıdır. Naxışın həm şaquli, həm də üfüqi uzunluqlarından daha uzun kvadrat ardıcıllıqlar ola bilər. Məsələn, yuxarıdakı naxışda F hərfindən, 8 istiqamətə doğru ən uzun öz-özünü üst-üstə düşməyən ardıcıllıqlardakı sətirlər aşağıdakılardır.
FGHEFKDEJCHIBGLAFJBFIDGJAHKBELCFEHGFALGBIHCJEDKFBJFCLEBKHAJGDI
Xəmir parçaları ilə dolu boğulmadan əvvəl sehrli tılsımı tapacaq bir proqram yazın.
Giriş verilənləri
Giriş bir sıra datasetlərdən ibarətdir. Hər dataset, naxışın ölçüsünü göstərən iki tam ədəd h və w ilə başlayır, ardından h sətir w böyük hərflərdən A ilə Z arasında olan hərflərlə davam edir ki, bunlar ponçik üzərindəki naxışı göstərir. Sizə 3 ≤ h ≤ 10 və 3 ≤ w ≤ 20 olduğunu qəbul edə bilərsiniz.
Girişin sonu iki sıfır olan bir sətirlə göstərilir.
Çıxış verilənləri
Hər dataset üçün sehrli tılsımı çıxış edin. Əgər eyni uzunluqda bir neçə ən uzun sətir varsa, lüğət sırasına görə birinci olan tılsım olmalıdır. Tılsımın ən azı iki hərf uzunluğunda olduğu bilinir. Heç bir tılsım tapılmadıqda, 0 (sıfır) çıxış edin.