İttifaqlar
Fantaziya dünyasında, düzbucaqlı bir ada var. Adanın ölçüləri R mil və C mildir və bu ada R×C ölçüsündə sahələrə bölünmüşdür. Bəzi sahələr boşdur, digərlərində isə elf, insan, cırtdan və hobbit kəndləri yerləşir. Hər sahədə ən çox bir kənd ola bilər. İki kənd, əgər sahələri bir tərəfi paylaşırsa, qonşu sayılır.
Son zamanlarda kəndlər Böyük Şərdən qorxmağa başladılar. Daha təhlükəsiz olmaq üçün hər kənd bəzi qonşuları ilə hərbi ittifaqlar qurmağa qərar verdi. İttifaq yalnız iki qonşu kənd arasında qurula bilər və bu qarşılıqlı və simmetrik bir razılaşmadır.
Kənddə yaşayan növlərə görə, sakinlər yalnız müəyyən bir ittifaq konfiqurasiyası qurulsa özlərini təhlükəsiz hiss edəcəklər:
Elfler özlərinə güvənirlər və yalnız bir ittifaqa ehtiyac duyurlar.
İnsan kəndləri iki qonşu ilə ittifaq tələb edir. Bundan əlavə, kəndin iki əks tərəfini açıq qoymaq taktiki səbəblərdən pisdir. Buna görə də, müttəfiq qonşular kəndin əks tərəflərində yerləşə bilməzlər.
Cırtdanlar üç qonşu ilə ittifaq tələb edir.
Hobbitlər çox qorxurlar və dörd qonşularının hamısı ilə ittifaqa ehtiyac duyurlar.
Başqa sözlə, insanlar istisna olmaqla, hər kənd müəyyən sayda ittifaq tələb edir, lakin hansı qonşuların müttəfiq olacağına əhəmiyyət vermir. İnsanlar üçün əlavə bir məhdudiyyət var: müttəfiq qonşular kəndin əks tərəflərində olmamalıdır.
Şərtlər xəritədə kəndin mövqeyindən asılı olmayaraq yerinə yetirilməlidir. Məsələn, bir cırtdan kəndi üç ittifaq istəyir. Əgər sahildə yerləşirsə, bu, onun üç qonşusu ilə ittifaqa malik olması deməkdir. Əgər adanın küncündə bir cırtdan kəndi varsa, onun sakinləri heç vaxt özlərini təhlükəsiz hiss etməyəcəklər.
Verilmiş ada təsviri üçün, bütün adanın sakinlərinin özlərini təhlükəsiz hiss etmələri üçün ittifaqların qurulmasının mümkün olub-olmadığını müəyyən etmək sizin vəzifənizdir. Müsbət cavab halında, sizin vəzifəniz həm də bir uyğun ittifaq konfiqurasiyası təklif etməkdir. Bir neçə həll yolu varsa, istənilən birini seçin.
Giriş verilənləri
Girişin ilk sətri adanın ölçüsünü göstərən iki tam ədəd R və C ehtiva edir. Növbəti R sətir adanın təsvirini kodlayır. Hər sətir C boşluqla ayrılmış 0 ilə 4 arasında olan rəqəmlərdən ibarətdir:
0 yaşayışsız sahəni bildirir,
1 elf kəndini bildirir,
2 insan kəndini bildirir,
3 cırtdan kəndini bildirir,
4 hobbit kəndini bildirir.
(Qeyd edək ki, girişdəki rəqəm həmişə həmin kənd üçün tələb olunan ittifaqların sayına uyğun gəlir.)
Məhdudiyyətlər
Bütün test hallarında 1 ≤ R, C ≤ 70 olduğunu fərz edin.
55 xal dəyərində olan test hallarında min(R, C) ≤ 10. Bunlardan 15 xal dəyərində olan test hallarında R·C ≤20.
Başqa bir 10 xal dəyərində olan test halları yalnız yaşayışsız sahələr və insan kəndləri olan xəritələri ehtiva edir. (Bu dəst 55 xal dəyərində olan test hallarında daxil deyil.)
Çıxış verilənləri
Əgər həll yolu yoxdursa, bir sətirdə "Impossible!" (aydınlıq üçün dırnaq işarələri) yazısını çıxarın. Əks halda, ittifaqların bir uyğun xəritəsini aşağıdakı formatda çıxarın.
Hər bir sahə çıxışda 3×3 simvollar matrisi kimi görünməlidir. Əgər sahə yaşayışsızdırsa, müvafiq hissə . (nöqtə) simvolları ilə doldurulacaq. Əgər sahədə kənd varsa, kəndi təmsil edən ortada O (böyük hərf O) simvolu olmalıdır və müttəfiqlərinin konfiqurasiyasını təmsil edən X (böyük hərf X) simvolları olmalıdır. Matrisin qalan hissəsi . (nöqtə) simvolları ilə doldurulmalıdır.
Hər kənd növü üçün ittifaqların bütün mümkün düzülüşləri aşağıdakı şəkildə göstərilmişdir.
