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

<syntaxhighlight lang="python" line>

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

1. 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")

</syntaxhighlight>