Pracsiu Dan (dnprx) Sus pe cerul nopții, stelele strălucitoare apar în roiuri de diferite forme. Un roi este un grup nevid de stele vecine, adiacente în direcție orizontală, verticală sau diagonală. Un roi nu poate face parte dintr-un roi mai mare. Roiurile pot fi similare. Două roiuri sunt similare dacă au aceeași formă și număr de stele, indiferent de orientarea lor. În general, numărul de orientări posibile pentru un roi este de opt, așa cum exemplifică Figura 1, în care se văd opt roiuri similare.
Cerul nopții este reprezentat printr-o matrice bidimensională binară. O celulă conține cifra 1 dacă are o stea, sau cifra 0 în caz contrar.
Cerința
Având o hartă a cerului, marcați toate grupurile de stele cu litere mici. Grupurile similare trebuie marcate cu aceeași literă; grupurile nesimilare trebuie marcate cu litere diferite. Marcați un grup cu o literă mică prin înlocuirea fiecărui 1 din grup cu acea literă mică. Marcarea se va face astfel: se parcurge matricea binară asociată cerului de sus în jos și de la stânga la dreapta. Primul grup găsit îl veți marca folosind litera a, al doilea găsit și nesimilar cu primul în veți marca cu b ș.a.m.d.
Date de intrare
Fișierul de intrare starrynight.in conține pe prima linie n reprezentând numărul de linii ale matricei, pe a doua linie m reprezentând numărul de coloane ale matricei. Harta cerului este apoi dată prin câte m valori binare aflate pe următoarele n linii.
Date de ieșire
Fișierul de ieșire starrynight.out va conține aceeași hartă, dar grupurile sunt marcate așa cum s-a descris în cerință.
Restricții și precizări
2 ≤ n, m ≤ 100- Numărul de grupuri este de cel mult
500 - Numărul de grupuri nesimilare este cel mult
26(pentru a putea fi marcate de laalaz)
Exemplu:
starrynight.in
23 15 10001000000000010000000 01111100011111000101101 01000000010001000111111 00000000010101000101111 00000111010001000000000 00001001011111000000000 10000001000000000000000 00101000000111110010000 00001000000100010011111 00000001110101010100010 00000100110100010000000 00010001110111110000000 00100001110000000100000 00001000100001000100101 00000001110001000111000
starrynight.out
a000a0000000000b0000000 0aaaaa000ccccc000d0dd0d 0a0000000c000c000dddddd 000000000c0b0c000d0dddd 00000eee0c000c000000000 0000e00e0ccccc000000000 b000000e000000000000000 00b0f000000ccccc00a0000 0000f000000c000c00aaaaa 0000000ddd0c0b0c0a000a0 00000b00dd0c000c0000000 000g000ddd0ccccc0000000 00g0000ddd0000000e00000 0000b000d0000f000e00e0b 0000000ddd000f000eee000
Explicație
Harta cerului are 23 de linii și 15 coloane. Datele de intrare corespund cu următoarea imagine:
Răspunsul corespunde următoarei imagini:
