1451 - Iceberg

Cerinţa

Se dă o matrice reprezentând o zonă dintr-un ocean ce conține un iceberg; valorile egale cu 1 fac parte din iceberg, iar cele egale cu 0 reprezintă apă.

Se știe că icebergul este înconjurat de apa (nu există nici o valoare de 1 pe marginea matricei) și că într-un interval de timp se topesc toate zonele icebergului care au cel puțin doua laturi vecine cu apa.

Determinați și afișați cate intervale de timp sunt necesare ca icebergul să se topească în întregime. De asemenea, afișați pentru fiecare interval de timp câte poziții de gheață are icebergul la începutul intervalului.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi o matrice de n linii și n coloane reprezentând zona icebergului.

Date de ieşire

Dacă datele sunt introduse corect,pe ecran se va afișa :"Datele sunt introduse corect.",apoi pe un rând nou numărul t reprezentând numărul de intervale de timp și t numere naturale reprezentând suprafața ghețarului la începutul fiecărui interval.În cazul contrar,se va afișa pe ecran "Datele nu corespund restricțiilor impuse.".

Restricții și precizări

• 1 ⩽ N ⩽ 31
• Elementele de pe marginile matricii sunt tot timpul 0

Exemplu

Intrare

7

0 0 0 0 0 0 0

0 1 1 1 1 1 0

0 0 1 1 1 0 0

0 0 1 1 1 0 0

0 1 1 1 1 1 0

0 0 0 0 0 0 0

0 0 0 0 0 0 0

Ieșire

Datele sunt introduse corect.

4

16

12

8

2

Explicație

După primul interval de timp ghețarul arată astfel:

0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 0 1 1 1 0 0
0 0 1 1 1 0 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0

După cel de-al doilea interval de timp ghețarul arată astfel:

0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 0 1 1 1 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0

După cel de-al treilea interval de timp ghețarul arată astfel:

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

iar la pasul următor se topește de în întregime.

Rezolvare

def validare_matrice(matrice):
    n = len(matrice)
    # verificăm dacă matricea este pătratică și are dimensiunea între 1 și 31
    if not all(len(row) == n for row in matrice) or n < 1 or n > 31:
        return False
    # verificăm dacă marginile matricei conțin doar valori de 0
    if not all(matrice[0][j] == 0 and matrice[n-1][j] == 0 and matrice[i][0] == 0 and matrice[i][n-1] == 0
               for i in range(n) for j in range(n)):
        return False
    # verificăm dacă matricea conține doar valori de 0 și 1
    if not all(val in [0, 1] for row in matrice for val in row):
        return False
    # verificăm dacă icebergul este înconjurat de apă
    for i in range(1, n-1):
        for j in range(1, n-1):
            if matrice[i][j] == 1 and all(matrice[i+di][j+dj] == 0 for di, dj in [(0,1), (1,0), (0,-1), (-1,0)]):
                return False
    return True

def topire_iceberguri(matrice):
    n = len(matrice)
    S = sum(row.count(1) for row in matrice)  # calculăm inițial numărul de celule din iceberg
    v = [S]  # adăugăm numărul inițial de celule în lista de soluții
    while S > 0:  # repetăm până când icebergul a fost complet topit
        for i in range(1, n-1):
            for j in range(1, n-1):
                if matrice[i][j] == 1:  # dacă celula este o parte din iceberg
                    contor = 0
                    if matrice[i-1][j] == 0: contor += 1  # dacă celula de sus este apă
                    if matrice[i+1][j] == 0: contor += 1  # dacă celula de jos este apă
                    if matrice[i][j-1] == 0: contor += 1  # dacă celula din stânga este apă
                    if matrice[i][j+1] == 0: contor += 1  # dacă celula din dreapta este apă
                    if contor >= 2:  # dacă icebergul are mai mult de o celulă de apă învecinată
                        S -= 1  # scădem numărul de celule din iceberg
                        matrice[i][j] = 2  # marcam celula curenta ca fiind topita
        v.append(S)  # adăugăm numărul de celule din iceberg în lista de soluții
        for i in range(1, n-1):
            for j in range(1, n-1):
                if matrice[i][j] == 2:
                    matrice[i][j] = 0  # resetăm celulele topite la valoarea de apă
    return v

if __name__ == '__main__':
   # citim matricea de la tastatură
    n = int(input())
    matrice = []
    for i in range(n):
        linie = list(map(int, input().split()))
        matrice.append(linie)

    # validăm matricea
    if not validare_matrice(matrice):
       print("Datele nu corespund restricțiilor impuse.")
    else:
       solutie = topire_iceberguri(matrice)
       print("Datele sunt introduse corect.")
       print(len(solutie)-1)
    for t in solutie[:-1]:
        print(t)