Şəkil Sıxılması#1817
İkiölçülü şəkilləri sıxışdırmaq üçün strategiyalar tez-tez oxşarlığı yüksək olan sahələrin tapılmasına əsaslanır. Bu məsələdə biz şəkilin ierarxik dekompozisiyasına əsaslanan xüsusi bir yanaşmanı araşdıracağıq. Sadəlik üçün yalnız aşağıdakı kimi bitmap şəkilləri nəzərdən keçirəcəyik:
Şəkil ağac kimi kodlaşdırılır və kök bütün şəkil sahəsini təmsil edir. Əgər hansısa bir sahə monoxromdursa, onda həmin sahə üçün olan düyün yarpaqdır və həmin sahənin rəngini saxlayır. Əks halda, sahə mərkəzindən dörd hissəyə bölünür və bu yanaşma hər kvadrant üçün rekursiv tətbiq olunur. Qeyri-yarpaq düyün üçün, onun dörd övladı ardıcıllıqla yuxarı-sağ, yuxarı-sol, aşağı-sol, aşağı-sağ kvadrantları təmsil edir. Məsələn, aşağıda həmin şəkilin ağac kodlaşdırılması verilmişdir.
Əsas şəkil monoxrom deyil, buna görə dörd kvadranta baxdıq. Yuxarı-sağ kvadrant monoxrom ağdır, buna görə kök düyünün ilk övladı 0 qiymətli yarpaqdır. Yuxarı-sol kvadrant monoxrom deyil, buna görə dörd altkvadranta daha bölünür, onların hər biri isə trivial monoxromdur. Bu altqolda yarpaq dəyərləri 0, 0, 1, 0 olur. Son iki kvadrant isə uyğun olaraq 0 və 1 olan monoxrom yarpaqlardır.
Daha böyük bir nümunə kimi, aşağıda 8x8 ölçülü bir şəkil və onun ağac kodlaması verilmişdir.
Buraya qədər təsvir edilən sıxışdırma sxemi itkisizdir, lakin bu yanaşmanı itgili sıxışdırma üçün də istifadə etmək olur. Monoxrom sahəyə qədər dekompozisiyanı davam etdirmək əvəzinə, məsələn, kimi bir hədd istifadə olunur və hər hansı bir sahədə rənglərin istənilən birindən ən azı bu faiz varsa, həmin sahə üçün yarpaq yaradılır. Məsələn, aşağıda həmin 8x8 şəkilin həddi ilə kodlaşdırılması göstərilmişdir.
Qeyd edin ki, əsas şəkilin yuxarı-sol kvadrantının -i qaradır və buna görə kökün ikinci övladı 1-dir, həmçinin əsas şəkilin aşağı-sol kvadrantının -dən çoxu ağdır və buna görə kökün üçüncü övladı 0 olur. Lakin, əsas şəkilin yuxarı-sağ kvadrantında nə ağ, nə də qara -ə çatmır, buna görə rekursiv dekompozisiya davam edir, amma bu dörd altkvadrantın hər biri həddini aşır və yarpağa çevrilir. Əgər bu yeni itgili kodlaşdırmaya əsasən şəkili geri dekompress etsək, aşağıdakı nəticə alınar.
Sizin məqsədiniz, ilkin bitmap şəkli və xüsusi bir faiz həddi verildikdə, bu itgili sıxışdırma sxemindən yaranan şəkili müəyyən etməkdir.
Giriş bir sıra məlumat dəstlərindən ibarətdir, axırda yalnız 0 olan sətr gəlir. Hər məlumat dəsti və dəyərləri olan sətrlə başlayır; burada bitmapın eni, isə faiz həddidir. Şəkillər hər zaman kvadrat olacaq və 1 \leq W \leq 64 olmaqla iki qüvvəti həddindədir. Hədd tam ədəddir və 51 \leq T \leq 100 şərtlərini ödəyir. və sətrinin ardınca əlavə olaraq sətr gəlir, hər sətr yalnız 0 və 1 simvollarından ibarət uzunluqda bitmap sətridir və şəkilin yuxarıdan aşağıya olan sətrlərini göstərir.
Hər məlumat dəsti üçün əvvəlcə "Image 1:" şəklində bir sətr çap edin, şəkilləri 1-dən başlayaraq nömrələyin. Sonra isə sətr çap olunmalıdır, hər sətrdə əldə olunan bitmapın müvafiq sətri simvollarla, yuxarıdan aşağıya şəkildə göstərilməlidir.
Nümunə 1