Fişierul intrare/ieşire:matricen.in, matricen.outSursăAlgoritmiada 2010, Runda Finala
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.625 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Matricen

Anul acesta Mos Craciun v-a facut un cadou mai ciudat, anume o matrice binara A cu N linii si N coloane. Totusi, matricele interesante sunt acele matrice care pe fiecare linie au numai elemente egale. Dan Craciun, fratele lui Mos Craciun va roaga sa il ajutati cu o problema pentru a va pune o vorba buna la mos. Dan va pune la dispozitie Q submatrice ale matricei initiale si va roaga sa aflati pentru fiecare submatrice numarul minim de operatii care trebuie efectuate astfel incat submatricea rezultata in urma efectuarii operatiilor sa fie interesanta. In cadrul unei operatii puteti interschimba oricare doua elemente din submatrice. Dan va furnizeaza coltul stanga-sus al submatricei precum si coltul dreapta-jos al ei. Daca (L1, C1) este coltul stanga-sus si (L2, C2) este coltul dreapta jos, atunci submatricea este formata din elemetele Ai,j, unde L1 ≤ i ≤ L2 si C1 ≤ j ≤ C2.

Date de intrare

Fişierul de intrare matricen.in contine pe prima linie doua numere naturale N si Q, separate printr-un singur spatiu, avand seminificatia din enunt. Urmeaza apoi N linii cu cate N elemente 0 sau 1 reprezentand matricea A. Elementele unei linii sunt separate de cate un singur spatiu. In continuare se gasesc Q linii reprezentand intrebarile lui Dan Craciun. Fiecare astfel de linie contine patru numere naturale L1, C1, L2 si C2, separate printr-un singur spatiu. Primele doua numere reprezinta linia si coloana corespunzatoare coltului stanga-sus al submatricei, iar ultimele doua linia si coloana coltului dreapta-jos.

Date de ieşire

În fişierul de ieşire matricen.out veti afisa Q linii, pe fiecare linia i aflandu-se numarul minim de interschimbari ce trebuie realizat pentru cea de i-a submatrice din fisierul de intrare. Daca nu exista solutie se va afisa -1.

Restricţii

  • 1 ≤ N ≤ 300
  • 1 ≤ Q ≤ 50 000
  • Pentru 50% din teste Q ≤ 1000

Exemplu

matricen.inmatricen.out
3 3
0 0 0
0 1 0
1 1 0
2 1 3 3
1 2 2 3
1 1 1 3
1
-1
0

Explicaţie

Pentru prima submatrice se poate interschimba elementul de pe pozitia (2, 2) cu cel de pe pozitia (3, 3). Pentru a doua submatrice nu avem solutie de aceea afisam -1. A treia submatrice contine deja o linie in care toate elementele sunt egale, deci nu mai trebuie sa efectuam nicio operatie.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content