Rezolvare PBinfo #3727

O matrice pătratică de dimensiuni N * N cu N par și elemente din mulțimea {0,1} se numește tablă de șah dacă oricare două celule vecine pe o linie sau pe o coloană au valori diferite (cu alte cuvinte, dacă nu există două valori egale alăturate).

De ziua ei, Victor i-a cumpărat Elisabetei o astfel de matrice A, care nu este neapărat tablă de șah. Aflând despre pasiunea ei, acesta vrea acum să transforme matricea A într-o tablă de șah. Timpul fiind limitat, el poate efectua doar următoarele tipuri de operații asupra matricei:
1. Interschimbă liniile i și j din A (celelalte linii rămân neschimbate, iar valorile din interiorul liniilor i și j rămân neschimbate și își păstrează ordinea). Operația are sens pentru 1 ≤ i, j ≤ N.
2. Interschimbă coloanele i și j din A (celelalte coloane rămân neschimbate, iar valorile din interiorul coloanelor i și j rămân neschimbate și își păstrează ordinea). Operația are sens pentru 1 ≤ i, j ≤ N.

Cerința

Dorind s-o impresioneze pe Elisabeta, Victor apelează la voi, programatori renumiți, să-l ajutați în a transforma matricea A într-o tablă de șah. Pentru aceasta, Victor are nevoie de următoarele informații:
1. Poate fi transformată matricea A în tablă de șah?
2. Care este numărul minim de operații necesare pentru a duce la îndeplinire acest scop?
3. Care ar fi o succesiune de operații care transformă matricea A într-o tablă de șah?

În cazul ultimei cerințe, pentru a intra în grațiile lui Victor va trebui ca numărul de operații efectuate să fie minim. Totuși, chiar și un număr neminim de operații va fi răsplătit, însă nu într-atât de mult.

Vi se dau două numere P, T și T matrice A, reprezentând mai multe instanțe ale problemei. Pentru fiecare matrice A dintre cele T va trebui să rezolvați cerința cu numărul P∊{1,2,3} dintre cele listate mai sus.

Date de intrare

Pe prima linie se găsesc două numere întregi pozitive P și T, reprezentând numarul cerinței de rezolvat și, respectiv, numărul de scenarii pentru care va trebui să rezolvați problema. Urmează cele T instanțe ale problemei, fiecare fiind compusă din N + 1 linii: pe prima linie se va afla numarul N, iar pe următoarele N linii câte N cifre binare neseparate prin spații, reprezentând câte o linie a matricei A.

Date de ieșire

Pentru fiecare dintre cele T instanțe se va afișa răspunsul, începând de la o linie nouă, după cum urmează:
1. Dacă P = 1, atunci se va afișa pe o singură linie 1 dacă matricea A poate fi transformată în tablă de șah, și 0 altfel.
2. Dacă P = 2, atunci se va afișa pe o singură linie un întreg reprezentând numărul minim de interschimbări de linii și/sau coloane necesare pentru a transforma matricea A în tablă de șah.
3. Dacă P = 3, atunci se va afișa pe o linie un număr X. Apoi, pe fiecare dintre următoarele X linii se va afișa câte o interschimbare de linii sau coloane, după următorul format: L i j are semnificația că liniile i și j se interschimbă, iar C i j are semnificația că se interschimbă coloanele i și j. Matricea obținută după aplicarea celor X operații asupra lui A în ordinea dată trebuie să fie o tablă de șah.

Restricții și precizări

• 1 ≤ T ≤ 350
• 1 ≤ N ≤ 1 000
• N este par.
• Pentru cerințele de tip P = 2 și P = 3 se garantează că matricea A poate fi transformată în tablă de șah folosind interschimbări de linii și/sau coloane.
• Suma valorilor N pentru cele T scenarii nu depășește 2.000.
• Pentru 40 de puncte, P = 1
• Pentru alte 34 de puncte, P = 2
• Pentru alte 26 de puncte, P = 3
• Dacă există mai multe soluții, oricare este considerată corectă.
• Dacă numărul X de operații folosite nu este minim, atunci se acordă 50% din punctajul pe test.

Exemplul 1:

Intrare

1 3
2
11
11
4
1100
1100
0011
0011
2
10
01

Ieșire

0
1
1

Explicație

Avem P = 1, deci pentru cele T = 3 instanțe se cere numai dacă se pot transforma în tablă de șah prin interschimbări de linii și/sau coloane. Pentru prima instanță acest lucru nu este posibil, deoarece nu avem niciun 0 în matrice. Pentru cea de-a doua instanță, putem efectua următoarele operații:

Pentru ultima instanță, matricea A este deja tablă de șah.

Exemplul 2:

Intrare

2 2
4
1100
1100
0011
0011
2
10
01

Ieșire

2
0

Explicație

Pentru al doilea exemplu avem P = 2, deci pentru cele T = 2 instanțe se cere numărul minim de operații pentru a le transforma în tablă de șah. Pentru prima instanță, o soluție cu 2 operații este prezentată mai sus, și nu există soluții mai scurte. Pentru cea de-a doua instanță, matricea este deja tablă de șah, deci răspunsul este 0.

Exemplul 3:

Intrare

3 2
4
1100
1100
0011
0011
2
10
01

Ieșire

3
L 2 4
C 2 3
L 1 2
0

Explicație

Al treilea exemplu este exact ca anteriorul, numai că avem P = 3, deci trebuie tipărite exact care sunt operațiile ce aduc matricea la forma de tablă de șah. Pentru punctaj maxim pe acest exemplu, ar fi obligatoriu să afișăm o soluție cu 2 operații (adică număr minim), cum ar fi cea de mai sus. Cu toate acestea, cu scop demonstrativ, noi venim cu o soluție compusa din 3 operații prin care obținem doar 50% din punctaj: