Fişierul intrare/ieşire:	siruri3.in, siruri3.out	Sursă	ONI 2018, clasa a 10-a, ziua 1
Autor	Adrian Budau	Adăugată de	Laura Georgescu •laurageorgescu
Timp execuţie pe test	0.075 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Siruri3

Fie M un tablou bidimensional (matrice), format din N linii şi N coloane, având elemente din mulţimea {0, 1}. Liniile şi coloanele acestui tablou sunt numerotate de 1 la N. Un drum de lungime K în acest tablou este un şir de perechi (x_i, y_i), cu i de la 1 la K, cu următoarele proprietăţi:

• x_i şi y_i sunt valori numere naturale din intervalul [1, N], pentru i de la 1 la K
• (|x_i - x_i+1|=1 şi y_i=y_i+1) sau (|y_i - y_i+1|=1 şi x_i=x_i+1), pentru i de la 1 la K-1

Altfel spus, un drum este o succesiune de poziţii în tablou astfel încât două poziţii consecutive sunt alăturate fie sus-jos, fie stânga-dreapta. Numim valoare a unui drum şirul de valori M[x_i][y_i], cu i de la 1 la K. Prin anagramă a unui şir de valori vom înţelege orice rearanjare a elementelor acestuia. De exemplu, dacă şirul iniţial conţine elementele (1, 0, 0, 1), atunci şirurile (1, 0, 0, 1), (1, 0, 1, 0), (1, 1, 0, 0), (0, 1, 1, 0) sunt anagrame ale acestuia.

Cerinta

Cunoscând dimensiunea N a tabloului, elementele tabloului M şi un şir S, compus din K elemente din mulţimea {0, 1}, determinaţi un drum în tabloul M, având ca valoare o anagramă a lui S, dacă acest drum există.

Date de intrare

Datele de intrare se citesc din fişierul siruri3.in, care are următoarea structură:

• pe prima linie se află două numere naturale N şi K, separate printr-un singur spaţiu, reprezentând dimensiunea tabloului, respectiv lungimea şirului S
• pe fiecare din următoarele N linii se află câte N valori din mulţimea {0, 1}, separate prin câte un spaţiu, reprezentând valorile tabloului M
• pe linia N+2 se află K numere, din mulţimea {0, 1}, separate prin câte un spaţiu, reprezentând valorile şirului S.

Date de ieşire

Datele de ieşire se vor scrie în fişierul siruri3.out, astfel:

• dacă nu există niciun drum care satisface cerinţa problemei, atunci se va scrie valoarea -1
• dacă există un astfel de drum, atunci se vor scrie, pe linii separate, K perechi de valori x_i y_i, din mulţimea {1,2, ...,N}, separate printr-un singur spaţiu, reprezentând drumul determinat.

Restricţii

• 1 ≤ N ≤ 100
• 1 ≤ K ≤ 10⁵
• Elementele tabloului M şi ale şirului S sunt elemente din mulţimea {0, 1}.
• Pentru teste în valoare de 20 de puncte, şirul S se găseşte pe o linie sau pe o coloană a matricei, aşa cum este dat în fişierul de intrare sau în ordine inversă.
• Soluţia nu este unică, se acceptă orice soluţie.

Exemplu

Cum se trimit solutii?