Harada Wally
"Where’s Wally" adlı məşhur kitab seriyasını tanıyırsınızmı? Bu kitablar, yüzlərlə insanın təsvir olunduğu müxtəlif şəkillərlə doludur. Oxucuların vəzifəsi isə bu kütlə içində Wally adlı şəxsi tapmaqdır.
"Where’s Wally"ni iki ölçülü qrafik təsvirlərin naxış uyğunluğu kimi düşünə bilərik. Burada Wally-nin fiqurunu şəkildə axtarmaq lazımdır. "Where’s Wally"ni həll etmək üçün kompüter proqramı yazmaq maraqlı olardı, lakin bu asan iş deyil, çünki Wally şəkillərdə bir qədər fərqli görünə bilər. Bu fikirdən imtina edərək problemi daha asan həll edilə bilən bir formaya gətiririk. Sizdən qrafik naxış uyğunluğu probleminin daha sadə bir versiyasını həll etməyiniz tələb olunur.
Bir şəkil və bir naxış verilir. Hər ikisi bitlərdən ibarət düzbucaqlı matrislərdir (əslində, naxış həmişə kvadrat şəklindədir). 0 ağ, 1 isə qara deməkdir. Buradakı problem, naxışın şəkildə neçə dəfə meydana gəldiyini saymaqdır, yəni şəkildə naxışla tam uyğun gələn kvadratların sayını tapmaqdır. 90 dərəcə və ya onun çoxluqları ilə döndərilmiş və/və ya güzgü görüntüsü yaradaraq çevrilmiş naxışlar da nəzərə alınmalıdır.
Giriş verilənləri
Giriş, hər biri aşağıdakı formatda olan datasetlər ardıcıllığıdır.
w h p şəkil məlumatları naxış məlumatları
Datasetin ilk sətri üç müsbət tam ədəd w, h və p-dən ibarətdir. w şəkilin eni, h isə hündürlüyüdür. Hər ikisi bitlərin sayında hesablanır. p naxışın eni və hündürlüyüdür. Naxış həmişə kvadrat şəklindədir. Siz 1 ≤ w ≤ 1000, 1 ≤ h ≤ 1000 və 1 ≤ p ≤ 100 olduğunu qəbul edə bilərsiniz.
Növbəti h sətir şəkili verir. Hər sətir w/6 (bu, (w+5)/6-ya bərabərdir) simvoldan ibarətdir və şəkilin üfüqi sətirinə uyğun gəlir. Bu simvolların hər biri şəkil sətirində soldan sağa doğru altı biti təmsil edir və BASE64 kodlaşdırma formatının bir variantında kodlanır. Kodlaşdırma qaydası aşağıdakı cədvəldə verilmişdir. Cədvəldəki dəyərin ən əhəmiyyətli biti şəkildəki ən sol biti təmsil edir. Son simvol həmçinin şəkilin enindən kənarda bir neçə biti də təmsil edə bilər; bu bitlər nəzərə alınmamalıdır.
Son p sətir naxışı verir. Hər sətir p/6 simvoldan ibarətdir və şəkil ilə eyni şəkildə kodlanır.
Üç sıfırdan ibarət bir sətir girişin sonunu göstərir. Girişin ümumi ölçüsü iki meqabaytı keçmir.
Çıxış verilənləri
Girişdəki hər dataset üçün, şəkildə uyğun gələn kvadratların sayını göstərən bir sətir çıxış edilməlidir. Çıxış sətirində əlavə simvollar olmamalıdır.
İki və ya daha çox uyğun gələn kvadratlar qarşılıqlı olaraq üst-üstə düşə bilər. Belə halda, onlar ayrı-ayrılıqda sayılır. Digər tərəfdən, tək bir kvadrat heç vaxt iki və ya daha çox dəfə sayılmır, məsələn, həm orijinal naxışa, həm də onun döndərilmiş versiyasına uyğun gəlsə belə.