cleanup

Cleanup este un joc logic pentru un singur jucător. O tablă cu $N$ linii și $N$ coloane este formată din câmpuri luminoase care pot avea două stări: aprins (valoarea 1) sau stins (valoarea 0). La începutul jocului anumite câmpuri sunt aprinse. La o mutare, jucătorul poate atinge orice câmp, ceea ce are ca efect schimbarea stării câmpurilor vecine pe direcțiile nord, sud, est și vest (dacă există). Starea câmpului atins nu se schimbă.

Scopul jucătorului este să stingă toate câmpurile. De exemplu, pornind de la tabla din Figura 1, jucătorul poate atinge câmpurile $(1,1)$, $(5,1)$ și $(5,5)$ pentru a obține configurația din Figura 2, apoi poate atinge câmpul $(2,5)$ pentru a obține configurația din Figura 3. Cu încă o atingere a câmpului $(3,4)$, tabla de joc se stinge.

Vom accepta că:

1. Putem atinge fiecare câmp cel mult o dată. Într-adevăr, atingerea unui câmp de un număr par de ori readuce tabla în starea ei inițială (înainte de aceste atingeri) și nu va avea efect în rezolvarea jocului, iar atingerea de un număr impar de ori este echivalentă cu o singură atingere.
2. Ordinea mutărilor nu contează. Tabla finală depinde doar de tabla inițială și de câmpurile atinse, nu de ordinea atingerilor.

De aceea, numim soluție o mulțime de câmpuri distincte prin a căror atingere tabla se stinge. Memorăm o soluție într-o matrice de $N \times N$ în care marcăm cu 1 câmpurile atinse de jucător și cu 0 pe celelalte. Pentru exemplul dat, soluția apare în figura 4.

Cerință

Cunoscând dimensiunea $N$ și starea inițială a tablei, se cere:

1. Numărul de soluții distincte prin care se poate goli toată tabla.
2. O soluție cu număr minim de mutări.

Date de intrare

Fișierul de intrare cleanup.in conține pe prima linie numerele naturale $C$ și $N$ separate prin spațiu. $C$ reprezintă numărul cerinței (1 sau 2), iar $N$ reprezintă dimensiunea tablei. Pe următoarele $N$ linii se găsesc câte $N$ numere având valoarea 0 sau 1, separate prin spații, reprezentând valorile inițiale ale câmpurilor tablei.

Date de ieșire

Fișierul de ieșire cleanup.out va avea următorul conținut, în funcție de valoarea lui $C$:

• Dacă $C = 1$, atunci pe prima linie se va tipări numărul de soluții distincte ale problemei.
• Dacă $C = 2$, atunci fișierul de ieșire va conține $N$ linii a câte $N$ valori 0 sau 1, separate prin câte un spațiu, reprezentând o soluție cu număr minim de mutări.

Restricții și precizări

• $1 \leq C \leq 2$
• $3 \leq N \leq 40$
• Se garantează că pentru fiecare fișier de intrare există cel puțin o soluție.
• Dacă există mai multe soluții cu număr minim de mutări, se acceptă oricare dintre ele.
• Pentru cerința 2, dacă soluția tipărită este corectă (stinge tabla), dar nu are număr minim de mutări, atunci acel răspuns valorează jumătate din punctajul oferit pe test.

Exemplul 1

cleanup.in

1 3
0 1 0
1 0 1
0 1 0

cleanup.out

8

Explicație

Cele 8 soluții sunt figurate mai jos.

Exemplul 2

cleanup.in

2 3
0 1 0
1 0 1
0 1 0

cleanup.out

0 0 0
0 1 0
0 0 0

Explicație

Singura soluție în numărul minim de mutări (1).