0211 - Spirala

Enunț

Se consideră tabloul bidimensional cu n linii şi n coloane ce conţine numere naturale cu cel mult patru cifre fiecare.

Cerinţa

Scrieţi un program care citeşte numărul natural n şi cele n*n elemente ale tabloului şi apoi afişează pe ecran elementele tabloului, separate prin câte un spaţiu, obţinute prin parcurgerea în spirală în sensul acelor de ceasornic.

Date de intrare

Fişierul de intrare spirala.in conţine pe prima linie numărul n, iar pe următoarele n linii câte n numere naturale separate prin spaţii, reprezentând elementele tabloului.

Date de ieşire

Dacă datele sunt introduse corect,în fișier se va afișa :"Datele sunt introduse corect.",apoi pe un rând nou fişierul de ieşire spirala.out va conţine pe prima linie elementele cerute, separate prin câte un spaţiu.În cazul contrar,se va afișa pe ecran "Datele nu corespund restricțiilor impuse.".

Restricții și precizări

• 2 ⩽ n ⩽ 23
• elementele tabloului sunt mai mici decât 1000

Exemplu

spirala.in

4

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

spirala.out

Datele sunt introduse corect.

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10

Rezolvare

from typing import List

def validare_date(n: int, a: List[List[int]]) -> bool:
    # Verificăm dacă n este între 2 și 23
    if n < 2 or n > 23:
        return False

    # Verificăm dacă matricea are n linii și n coloane
    if len(a) != n:
        return False
    for row in a:
        if len(row) != n:
            return False

    # Verificăm dacă toate elementele matricei au cel mult 4 cifre
    for row in a:
        for elem in row:
            if elem >= 10000:
                return False

    # Toate verificările au trecut, deci matricea este validă
    return True


def rezolvare_spirala(n: int, a: List[List[int]]) -> List[int]:
    # Inițializăm poziția curentă la colțul din stânga sus
    poz_i, poz_j = 0, 0

    # Inițializăm direcția de mers
    directii = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    dir_index = 0

    # Inițializăm lista rezultat
    rezultat = []

    # Parcurgem matricea în spirală
    for _ in range(n * n):
        # Adăugăm elementul curent în rezultat
        rezultat.append(a[poz_i][poz_j])

        # Marcam elementul curent ca fiind deja vizitat
        a[poz_i][poz_j] = None

        # Calculăm următoarea poziție în funcție de direcție
        urm_i = poz_i + directii[dir_index][0]
        urm_j = poz_j + directii[dir_index][1]

        # Dacă următoarea poziție este invalidă sau deja vizitată,
        # schimbăm direcția de mers
        if (not 0 <= urm_i < n) or (not 0 <= urm_j < n) or (a[urm_i][urm_j] is None):
            dir_index = (dir_index + 1) % 4
            urm_i = poz_i + directii[dir_index][0]
            urm_j = poz_j + directii[dir_index][1]

        # Actualizăm poziția curentă
        poz_i, poz_j = urm_i, urm_j

    # Returnăm lista rezultat
    return rezultat


# Funcția principală
if __name__ == "__main__":
    # Citim datele de intrare
    with open("spirala.in", "r") as fin:
        n = int(fin.readline())
        a = []
        for _ in range(n):
            row = list(map(int, fin.readline().split()))
            a.append(row)

    # Verificăm dacă datele de intrare sunt valide
    if not validare_date(n, a):
        with open("spirala.out", "w") as fout:
            fout.write("Datele nu corespund restricțiilor impuse.")
    else :

    # Rezolvăm problema
        rezultat = rezolvare_spirala(n, a)

    # Afișăm rezultatul
    with open("spirala.out", "w") as fout:
        fout.write("Datele sunt introduse corect.\n")
        fout.write(" ".join(str(elem) for elem in rezultat))
        fout.write("\n")