Enunțul problemei zigzag, de clasa a 7-a, dată în 2012 la ONI, se găsește pe PbInfo și .campion.

Rezumat zigzag

Trebuie să decodificăm un mesaj (șir de caractere), știindu-i cheia de codificare și lungimea. Metoda de codificare folosită se numește Rail Fence Cipher, și funcționează astfel: Folosind un caroiaj, începem să scriem mesajul din colțul stânga-sus, mergând pe diagonală în direcția dreapta-jos. După ce am scris un caracter pe ultima linie (care este cheia de codificare), schimbăm direcția în dreapta-sus. După ce atingem prima linie, schimbă direcția în dreapta-jos, și tot așa. La final, parcurgem caroiajul de sus în jos și de la stânga la dreapta, iar când găsim un caracter, îl adăugăm la mesajul codificat. De exemplu, codificarea lui "OLIMPIADA DE INFORMATICA" este "ODTL EAIIA MCMDIRAPANOIF", dacă folosim cheia 6:

Exemplu zigzag

Soluție zigzag

Am definit un struct numit Pos care reține informații despre celulele caroiajului: chr, caracterul scris în celula respectivă, id (explic imediat), lin și col (coordonatele sale). Citim cheia de sortare (key) și lungimea string-ului (n).

Apoi, construim un vector pos cu celule create după modul descris în enunț. Pentru asta am folosit trei variabile (lin, col, dir), ce reprezintă linia, coloana și respectiv direcția curentă. Variabila dir poate lua valorile +1 (dreapta-jos) și -1 (dreapta-sus). Inițial, lin și col primesc valoarea 1, iar dir devine -1. La fiecare pas, elementul curent din vector primește valorile curente pentru lin și col, iar câmpul id ia valoarea pasului curent (i). Apoi, actualizăm pe dir dacă e cazul, incrementăm pe col, iar la lin adăugăm dir.

Sortăm vectorul pos după criteriul cmp1, adică în ordine crescătoare după linie, și în caz de egalitate, crescătoare după coloană. Acum putem citi string-ul din fișierul de intrare, completând și câmpurile chr. După aceea, sortăm vectorul după criteriul cmp2 (crescător în funcție de id), pentru a-l readuce la ordinea inițială. Urmează să-l parcurgem, crescător, în mod obișnuit, și să afișăm chr-ul fiecărui element.

Sursă C++ zigzag

Dacă ai vreo nedumerire cu privire la problema zigzag, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!