Rəngli xəritə#3201
Əfsanəvi sehrli müəmmalı dünyaya girməzdən əvvəl xeyli şanslı olub xəritə əldə etdin. Xəritədə bütün araşdırma planlaşdırdığın sahə, o cümlədən bir neçə mürəkkəb sərhədli ölkələr göstərilib. Xəritə aydın çəkilib, amma yalnız sepya mürəkkəbindədir; hansı bölgənin hansı ölkəyə aid olduğunu tez müəyyən etmək çətindir və bu, sənə ciddi təhlükə yarada bilər. Sahəyə daxil olmamışdan əvvəl xəritəni rəngləməyə qərar verirsən. "Hazırlıqda bir çox şey asılıdır," deyirsən öz-özünə.
Hər bir ölkənin bir və ya bir neçə ərazisi var və hər ərazi çoxbucaqlıdır. Eyni ölkəyə məxsus ərazilər bir-birilə təmasda ola bilər və ya olmaya bilər — yəni ölkənin ayrı-ayrı əraziləri ola bilər. Eyni ölkəyə aid olan bütün ərazilər eyni rəngə boyanmalıdır. Bir rəngi bir neçə ölkəyə təyin edə bilərsən, amma qarışıqlığın qarşısını almaq üçün "bitişik" olan iki ölkəyə müxtəlif rənglər vermək lazımdır. İki ölkə o zaman "bitişik" sayılır ki, onların istənilən əraziləri sıfırdan fərqli uzunluğa malik sərhəd paylaşsın.
Xəritəni təsvir edilən qaydada rəngləmək üçün lazım olan minimal rəng sayını müəyyən edən proqram yaz.
Giriş bir neçə xəritə təsvirindən ibarətdir. Hər xəritə əvvəlcə ərazilərin ümumi sayı olan sətrə malikdir, sonra isə hər ərazinin təsviri verilir. müsbət tam ədəddir və -dən çox olmur.
təpəyə malik ərazi üçün məlumatlar aşağıdakı kimidir: - İlk hissə: \textbf{String}\;x_1\;y_1\;x_2\;y_2\;\ldots\;x_m\;y_m\;-1 - — ərazinin aid olduğu ölkənin (əlifba-rəqəm) adıdır. Ölkə adları azı bir, çoxu iyirmi simvoldan ibarətdir. Ölkənin bir neçə ərazisi varsa, adı hər ərazi məlumatında göstərilir. - Qalan hissədə hər təpə iki sıfırdan böyük olmayan tam ədədlə ( və koordinatları) verilir. Heç bir koordinat -i aşmır. - Hər çoxbucaqlı üçün təpələrin sayı -dən çox olmur.
Hər ərazi üçün təpələr ardıcıllıqla verilir; ərazi ardıcıl təpələrlə və sonuncu təpə ilə birinci təpənin birləşdirilməsi ilə formalaşır. Xəritənin ərazi siyahısı ərazi təsvir edildikdə bitir.
Çoxbucaqlılar sadədir, yəni konturları özlərini kəsmir və ya toxunmur. Heç iki çoxbucaqlı sıfırdan böyük sahə paylaşmır.
Xəritədə ölkələrin sayı -dan çox olmur.
Giriş yalnız bir sıfırdan ibarət sətrlə bitir.
Hər xəritə üçün, xəritəni yuxarıda təsvir edilən qaydada rəngləmək üçün lazım olan minimal rəng sayını göstərən bir sətr çıxar.
Nümunə 1