e-olymp
Məsələlər

Voronovun intiqamı

Voronovun intiqamı

Voronovun diskret diaqramı Voronov diaqramının törəməsidir. O nöqtələr çoxluğu ilə ifadə olunur. Hər bir təşkiledici hər hansı bir nöqtənin mərkəzində yerləşir. Hər bir nöqtə o təşkilediciyə aiddir ki, Manxetenə görə ona görə məsafəsi minimum olsun. İki (x1, y1) və (x2, y2) nöqtələri arasındakı d Manxeten məsafəsi növbəti düsturla hesablanır:

d = |x1 − x2| + |y1 − y2|

Sizdən verilmiş Voronovun diskret diaqramını hasil edən təşkiledicilər çoxluğunu tapmaq tələb olunur. Ondakı hər bir təşkiledici onun işarəsi olan kiçik hərflərlə verilir. Hər bir nöqtə onun aid olduğu təşkiledicisinin adı ilə verilir. Əgər nöqtənin ondan eyni məsafədə olan bir neçə təşkiledicisi olarsa, onda o nöqtəni seçmək lazımdır ki, adı ən kiçik olsun (yəni, ən kiçik simvol olsun).

Giriş verilənləri

Giriş verilənləri bir neçə testi ehtiva edir.

Hər bir test iki W (1W32) və H (1H32) tam ədədlərini – Voronovun diskret diaqramının genişliyini və yüksəkliyini ehtiva edir.

Hər bir növbəti H sətir Voronovun diskret diaqramını ifadə edən W hərfdən ibarətdir. Hər bir hərf bir nöqtəni verir.

Sonuncu sətir iki sıfır ehtiva edir və emal edilmir.

Çıxış verilənləri

Hər bir test üçün təşkiledicilərin koordinatlarını nümunədə göstərildiyi kimi verməli. Təşkiledicini ifadə edən hər bir sətir onun adını, həmçinin xy koordinatlarını ehtiva etməlidir. Təşkilediciləri onların təşkiledicilərinin adlarının əlifba sırasına görə vermək lazımdır. Koordinatlar sıfırdan başlayır, (0, 0) diaqramın yuxarı sol küncündə yerləşən nöqtənin mərkəzinin koordinatıdır.

Hər bir testin heç olmasa bir həlli var. Əgər bir neçə həll olarsa, onlardan hər hansı birini vermək olar.

Sonuncu test də daxil olmaqla hər bir testdən sonra boş sətir vermək lazımdır.

Zaman məhdudiyyəti 10 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
4 3
ooxx
ooxx
ooxx
4 1
null
4 4
aabb
aabb
ccdd
ccdd
0 0
Çıxış verilənləri
Case 1:
o 0 0
x 2 0

Case 2:
l 2 0
n 0 0
u 1 0

Case 3:
a 0 0
b 2 0
c 0 2
d 2 2