Editing 1702 - Cristale

Pietrele preţioase au fascinat  omenirea încă din timpuri străvechi iar cele mai renumite dintre ele, cristalele, au devenit atât simbolul durităţii cât şi al eternităţii. În urma unui studiu ştiinţific, pe un eşantion de formă dreptunghiulară se pot observa diferite tipuri de molecule, dispuse într-o geometrie perfectă, pe <code>M</code> rânduri a câte <code>N</code> molecule fiecare, aliniate una lângă alta. O formaţiune cristalizabilă este alcătuită din <code>3</code> molecule de acelaşi tip, învecinate două câte două, având una dintre cele patru forme din imaginea alăturată (fig.1).

Fiecare formaţiune este înconjurată de jur-împrejur, ca în fig.2, de un înveliş special format şi el din molecule identice, de alt tip decât cele din formaţiunea cristalizabilă pe care o înconjoară şi o izolează de restul formaţiunilor moleculare. În acest fel, fiecare moleculă din formaţiunea cristalizabilă se învecinează la Nord, Sud, Est şi Vest cu o moleculă din aceeaşi formaţiune cristalizabilă sau cu o moleculă din învelişul special.

Fiecare formaţiune cristalizabilă se bombardează cu raze <code>X</code> şi în acest fel are loc cristalizarea, proces prin care învelişul special se extinde peste formaţiunea cristalizabilă pe care o înconjoară, formând o singură structură din care se va dezvolta cristalul.

= Cerințe =

# Determinaţi numărul formaţiunilor cristalizabile ce pot fi identificate pe eşantionul analizat.
# Afişaţi eşantionul rezultat după cristalizare.

= Date de intrare =
Fișierul de intrare <code>cristale.in</code> conține pe prima linie un număr natural <code>c</code> reprezentând cerinţa care trebuie să fie rezolvată (1 sau 2). Pe cea de-a doua linie se află două numere naturale <code>M</code> şi <code>N</code>, separate printr-un spaţiu, având semnificaţia din enunţ. Pe următoarele <code>M</code> linii se află câte <code>N</code> numere naturale, separate prin câte un spaţiu, reprezentând moleculele din eşantionul analizat.

= Date de ieșire =
Dacă valoarea lui <code>c</code> este <code>1</code>, atunci se va rezolva numai cerinţa 1, caz în care pe prima linie a fişierului <code>cristale.out</code> va fi scris un număr natural reprezentând numărul formaţiunilor cristalizabile identificate pe eşantionul analizat. Dacă valoarea lui <code>c</code> este <code>2</code>, atunci se va rezolva numai cerinţa 2. În acest caz, fişierul de ieşire <code>cristale.out</code> va conţine pe fiecare dintre primele <code>M</code> linii, câte <code>N</code> numere naturale separate prin câte un spaţiu, reprezentând moleculele eşantionului rezultat după cristalizare.

= Restricții și precizări =

* <code>4 ≤ M,N ≤ 800</code> şi tipul fiecărei molecule este exprimat printr-un număr natural din intervalul <code>[1,16]</code>;
* pe marginea eşantionului nu pot fi identificate formaţiuni cristalizabile; există cel puţin o formaţiune cristalizabilă pe eşantionul analizat;
* eşantionul nu conţine formaţiuni cristalizabile lipite (cu celule vecine pe una din cele patru direcţii);
* pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.

= Exemplul 1 =
<code>cristale.in</code>
 1
 6 8
 5 6 6 1 5 2 6 5
 6 9 9 6 1 7 1 2
 6 6 9 6 3 4 1 6
 2 2 6 3 4 7 4 2
 8 8 2 4 7 7 4 6 
 8 2 7 2 4 4 2 5
<code>cristale.out</code>
 2

=== Explicație ===
Se va rezolva cerinţa 1 a problemei.

Eşantionul are <code>6</code> rânduri cu câte <code>8</code> molecule pe fiecare rând. Pe acest eşantion observăm o formaţiune cristalizabilă cu celule de tip <code>9</code>, izolată de învelişul special format din celule identice, toate de tip <code>6</code> şi o formaţiune cristalizabilă cu celule de tip <code>7</code>,  izolată de învelişul special format din celule identice, toate de tip <code>4</code>.

Formaţiunea de <code>3</code> molecule de tip <code>8</code> nu este o formaţiune cristalizabilă întrucât se află pe marginea eşantionului.

= Exemplul 1 =
<code>cristale.in</code>
 1
 6 8
 5 6 6 1 5 2 6 5
 6 9 9 6 1 7 1 2
 6 6 9 6 3 4 1 6
 2 2 6 3 4 7 4 2
 8 8 2 4 7 7 4 6 
 8 2 7 2 4 4 2 5
<code>cristale.out</code>
 2

=== Explicație ===
Se va rezolva cerinţa 1 a problemei.

Eşantionul are <code>6</code> rânduri cu câte <code>8</code> molecule pe fiecare rând. Pe acest eşantion observăm o formaţiune cristalizabilă cu celule de tip <code>9</code>, izolată de învelişul special format din celule identice, toate de tip <code>6</code> şi o formaţiune cristalizabilă cu celule de tip <code>7</code>,  izolată de învelişul special format din celule identice, toate de tip <code>4</code>.

Formaţiunea de <code>3</code> molecule de tip <code>8</code> nu este o formaţiune cristalizabilă întrucât se află pe marginea eşantionului.

<syntaxhighlight lang="python" line="1">
def is_valid_position(x, y, M, N):
    return 0 <= x < M and 0 <= y < N

def identify_crystalline_formations(sample, M, N):
    directions = [
        [(0, 0), (0, 1), (0, 2)],  # Orizontal
        [(0, 0), (1, 0), (2, 0)],  # Vertical
        [(0, 0), (0, 1), (1, 0)],  # L form
        [(0, 0), (1, 0), (1, 1)],  # Inverse L form
    ]
    
    formations = []
    
    for i in range(M):
        for j in range(N):
            for direction in directions:
                molecules = set()
                valid = True
                for dx, dy in direction:
                    x, y = i + dx, j + dy
                    if not is_valid_position(x, y, M, N):
                        valid = False
                        break
                    molecules.add(sample[x][y])
                
                if valid and len(molecules) == 1:
                    formations.append((i, j, direction))
    
    return formations

def apply_crystallization(sample, formations, M, N):
    for (i, j, direction) in formations:
        surrounding_type = None
        formation_type = sample[i][j]
        
        # Identify the surrounding type
        for dx, dy in direction:
            x, y = i + dx, j + dy
            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
                if is_valid_position(nx, ny, M, N) and sample[nx][ny] != formation_type:
                    surrounding_type = sample[nx][ny]
                    break
            if surrounding_type:
                break
        
        # Apply the crystallization
        if surrounding_type:
            for dx, dy in direction:
                x, y = i + dx, j + dy
                sample[x][y] = surrounding_type

def print_sample(sample):
    for row in sample:
        print(' '.join(map(str, row)))

# Exemplu de utilizare
M = 5
N = 5
sample = [
    [1, 1, 1, 2, 3],
    [1, 4, 2, 3, 2],
    [4, 2, 3, 2, 2],
    [2, 2, 3, 1, 4],
    [3, 1, 4, 4, 4],
]

formations = identify_crystalline_formations(sample, M, N)
print(f"Formațiuni cristalizabile: {formations}")
apply_crystallization(sample, formations, M, N)
print("Eșantion după cristalizare:")
print_sample(sample)
</syntaxhighlight>