Văran Tudor (tudorvaran) Cerința
Hackerul Gigel e pus pe șotii. Folosind un pachet de date corupt, acesta încearcă sa suprasolicite o rețea de n*n calculatoare dispuse sub forma unei matrice cu n rânduri și n coloane. El știe că fiecare calculator este conectat la calculatoarele adiacente(sus, dreapta, stânga, jos), fiecare calculator de pe rândul n este conectat la calculatorul de pe rândul 1 și aceeași coloană, și fiecare calculator de pe coloana n este conectat la cel de pe coloana 1 și aceeași linie.
Pentru a evita virușii nedoriți, calculatoarele din rețea nu pot prelucra pachete corupte și vor încerca pe cât posibil să le evite. Dacă un calculator primește un pachet corupt de la un calculator vecin, acesta îl va transmite mai departe în aceeași direcție ca cea alesă de calculatorul de la care a primit pachetul.
Se mai știe că administratorul rețelei a criptat câteva calculatoare, iar acestea nu vor accepta pachete corupte. Dacă un calculator încearcă sa trimită un pachet corupt unui calculator criptat operația va eșua, iar calculatorul respectiv va păstra pachetul până va primi o nouă comandă. Hackerul Gigel este foarte inteligent și poate da o comandă fiecărui calculator necriptat prin care să direcționeze pachetul de date corupt în una dintre cele patru direcții: Sus, Dreapta, Jos, Stanga.
Pentru a suprasolicita rețeaua, hackerul Gigel trebuie să găsească o succesiune de n calculatoare necriptate situate pe același rând sau aceeași coloană, pentru ca atunci când va trimite pachetul corupt spre acestea, ele să îl transmită mai departe la infinit.
Pachetul corupt se află inițial în calculatorul aflat pe rândul x și coloana y. Ajutați-l pe hackerul Gigel găsească o succesiune de comenzi prin care să suprasolicite rețeaua!
Date de intrare
Fișierul de intrare suprasolicitare.in conține pe prima linie numărul n, urmat de n linii, fiecare cu câte n numere având valorile 0 (calculator necriptat) sau 1 (calculator criptat). Pe linia n + 2 a fișierului se află coordonatele x și y ale calculatorului de unde începe Gigel să transmită pachetul de date corupt, separate printr-un spațiu.
Date de ieșire
Fișierul de ieșire va conține un număr natural Sol reprezentând numărul de comenzi pe care le transmite Gigel în rețea pentru a transmite pachetul. Pe următoarele Sol rânduri se află câte un cuvânt din mulțimea {'Sus', 'Dreapta', 'Jos', 'Stanga'} reprezentând direcția înspre care acesta trimite pachetul corupt.
Restricții și precizări
1 ≤ n ≤ 100- Orice soluție care duce la înghețarea rețelei este considerată corectă.
- O altă comandă decât cea din mulțimea
{'Sus', 'Dreapta', 'Jos', 'Stanga'}va duce la descoperirea pachetului de către administrator - Dacă valoarea lui
Soleste mai mare decât numărul de comenzi, se va acorda60%din punctaj. - Pentru teste în valoare de
50de puncte,n ≤ 10
Exemplu:
suprasolicitare.in
8 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 1 0 1 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 5 6
suprasolicitare.out
2 Sus Dreapta
Explicație
Pornind din calculatorul aflat la x = 5 și y = 6, pachetul se deplasează la calculatorul cu x = 1 și y = 6 de unde Gigel îl poate trimite într-un ciclu infinit pe rândul 1.
Succesiunea Sus, Stanga este de asemenea validă.