Altıbucaqlı sahələr
Mühəndis-memarlıq ixtisasını yeni bitirmiş bir mühəndis, maraqlı bir problemlə qarşılaşıb və bizdən kömək istəyib. Problem daha çox iqtisadi xarakter daşıyır, nəinki mühəndislik. Mühəndis bir neçə binanı infrastrukturla birləşdirməlidir. Təəssüf ki, investor bu yerlər arasındakı bütün torpağın sahibi deyil. Beləliklə, bəzi sahələr əvvəlcə alınmalıdır.
Torpaq, hər biri müstəqil bir hissə olan və eyni dəyərə malik olan düzgün altıbucaqlı torpaq sahələrinin şəbəkəsidir. Bəzi sahələr investora məxsusdur. Onlar dörd bitişik sahə təşkil edir, hər biri bir bina ehtiva edir və bu binalar bir-biri ilə birləşdirilməlidir. Sizə verilmiş dörd sahəni birləşdirmək üçün kifayət edəcək ən az torpaq sahələrinin sayını tapmaq lazımdır.
Bütün torpaq altıbucaqlı formadadır, hər bir hissəsi altı tərəfdən h sahə ehtiva edir. Yuxarıdakı şəkildə h = 4 olan torpaq təsvir olunub. Hərflərlə göstərilən sahələr birləşdirilməli olan dörd sahəni təmsil edir. Verilmiş nümunə üçün əlavə olaraq dörd sahə almaq kifayətdir. Mümkün həllərdən biri xaç işarələri ilə göstərilib.
Giriş verilənləri
Giriş məlumatları bir neçə testdən ibarətdir. Hər bir test torpağın ölçüsünü göstərən tam ədəd h (2 ≤ h ≤ 20) ilə başlayır. Sonra torpağın ayrı-ayrı "sətirlərini" təsvir edən 2h-1 sıra gəlir (həmişə şəkildəki kimi yönləndirilmişdir). Sətirlərdəki hər bir sahə boşluqdan fərqli bir simvolla göstərilir. Bu o deməkdir ki, birinci sətir h simvol, ikinci h+1 və s. ehtiva edir. Ən uzun sıra ortada 2h-1 simvol ehtiva edir. Sonra "uzunluq" azalır və son sıra yenidən h sahə ehtiva edir.
Sahə, investorun sahib olmadığı torpaqlar üçün nöqtə (".") və ya böyük hərflərdən biri "A", "B", "C" və ya "D" ilə göstərilir. Eyni hərflərin olduğu sahələr həmişə bir-biri ilə əlaqəlidir. Yəni bir sahənin iki istənilən sahəsi arasında həmişə bu sahənin sahələrindən keçən bir yol mövcuddur.
Torpaq sahələrini təyin edən simvollardan əlavə, sətirlər oxunabilirliyi artırmaq üçün istənilən mövqedə istənilən sayda boşluq ehtiva edə bilər. İki hərf (nöqtə) arasında həmişə ən azı bir boşluq mövcuddur. Torpağın təsvirindən sonra boş bir sıra gəlir, sonra növbəti test gəlir. Son testdən sonra sıfır ehtiva edən bir sıra gəlir.
Çıxış verilənləri
Hər bir test üçün bir sıra çıxarın - "You have to buy p parcels." cümləsi, burada p bütün dörd sahəni birləşdirmək üçün alınması lazım olan ən az torpaq sahələrinin sayıdır.
Sahələr yalnız alınmış sahələr vasitəsilə bir yol olduqda əlaqəli sayılır.