Zəncir Kodu
Qara-ağ (iki səviyyəli) bir təsvirin içində, birləşmiş qara piksellərdən ibarət qruplar obyektlər və ya ön plan kimi qəbul edilə bilər, ağ piksellər isə fon rolunu oynayır. Birləşmiş qara piksellərin hər bir qrupu, sərhədindəki piksellərin mövqelərini əks istiqamətdə, sərhədin istənilən nöqtəsindən başlayaraq sadalamaqla tam şəkildə təsvir edilə bilər. Bu piksellərin siyahısı, sadəcə siyahıdakı növbəti pikselə olan istiqamət kimi göstərilə bilər. Bu istiqamətlər siyahısına obyektin zəncir kodu deyilir və obyektin formasını dəqiq təsvir edir, mövqeyindən asılı olmayaraq.
Bir pikselin qonşu pikselə olan 8 mümkün istiqaməti var və bu istiqamətlərin təyin edilməsi təsadüfi olsa da, şəkil 1 standart konvensiyanı göstərir. 0 istiqaməti "sağda", 2 "dərhal yuxarıda" deməkdir və 1 45 dərəcədir, 0 və 2 arasını iki bərabər hissəyə bölür və s.
İki qara piksel, aralarındakı məsafənin kvadratı 2-dən kiçik və ya bərabərdirsə, qonşu hesab olunur. Bu, hər bir tam ədədi koordinatda piksel olan standart qrafik koordinat sisteminə əsaslanır. İki piksel, aralarında birləşmiş piksellərin ardıcıl bir yolu izlənə bilirsə, bağlı hesab olunur. Birləşmiş bir bölgə, bütün üzvlərin bir-birinə bağlı olduğu qara piksellər dəstidir. Birləşmiş bir bölgənin sərhəd pikselləri (bundan sonra sadəcə bölgə) qara olmayan ən az bir qonşusu (dörd kompas istiqamətində) olan bölgə daxilindəki pikseldir. Bu problem üçün, bölgədə "deliklər" olmadığını və yalnız bir sərhədin olduğunu qəbul edə bilərsiniz.
Bir bölgənin zəncir kodu sərhəddəki hər hansı bir piksel ilə başlaya bilər. Əks istiqamətdə sərhəddəki növbəti qonşu pikseli taparaq, istiqaməti (0-7) çıxış buferində saxlayaraq və sonra yeni piksel ilə prosesi davam etdirərək irəliləyir. Yenidən başlanğıc pikselə çatdıqda, zəncir kodu tamamlanır. Çıxış buferi, zəncir kodunu təşkil edən istiqamət dəyərlərini ehtiva edir və təsvirin hər hansı bir piksel mövqeyindən başlayaraq orijinal piksel dəstini yenidən yaratmaq mümkündür.
Məsələn, şəkil 2-dəki bölgənin zəncir kodu 446567001232-dir. Zəncir kodu bölgənin formasını birmənalı şəkildə təsvir edir, baxmayaraq ki, onun mövqeyi tamamilə məlum deyil. Perimetr və sahə (bölgədəki piksellərin sayı) kimi forma ilə əlaqəli ölçülər yalnız zəncir kodu təsvirindən birbaşa müəyyən edilə bilər. Sizə yalnız zəncir kodu verilmiş birləşmiş bölgənin sahəsini hesablayan bir proqram yazmalısınız.
Giriş verilənləri
Giriş, hər sətirdə bir zəncir kodu olan bir kolleksiya olacaq. Hər bir zəncir kodu ən çox 1000000 simvol ehtiva edir. Hər bir zəncir kodunun etibarlı bir bölgəni təsvir etdiyini və sərhədin öz-özünə kəsişmədiyini qəbul edə bilərsiniz.
Çıxış verilənləri
Girişdəki hər bir zəncir kodu üçün, bölgənin sahəsi (yəni ona aid olan piksellərin sayı) çıxışda öz sətirində çap olunacaq.