tsah

Tsah

== include(page="template/taskheader" task_id="tsah") ==

Poveste si cerinta...

O tabla de sah este o matrice binara de dimensiuni $NxN$, cu liniile si coloanele numerotate de la $1$ la $N$. Fiecare pozitie este ori neagra, daca suma numarului liniei si numarului coloanei este para, ori alba, in caz contrar. Figura de mai jos ilustreaza cum arata o tabla de sah pentru $N=1$, $N=2$ si $N=3$.
!problema/tsah?tsah.jpg!
 
Fiind data o matrice binara, gasiti dimensiunea celei mai mari table de sah localizata complet in interiorul matricii, precum si numarul de table de sah avand dimensiunea maxima (aceste table se pot suprapune partial).

h2. Date de intrare

...

Prima linie a fisierul de intrare $tsah.in$ contine un numar intreg $T$, reprezentand numarul de teste ce urmeaza. Fiecare test contine pe prima linie un numar intreg $N$, reprezentand numarul de linii si de coloane ale matricii date. Urmatoarele $N$ linii descriu matricea: fiecare linie contine $N$ caractere, care pot fi ori $'1'$ (reprezentand un patratel negru), ori $0$ (reprezentand un patratel alb). Matricea va contine cel putin un caracter $'1'$.

h2. Date de iesire

...

Pentru fiecare din cele $T$ teste, in ordinea din fisierul de intrare, veti afisa in fisierul de iesire $tsah.out$ o linie continand dimensiunea celei mai mari table de sah, urmata de un spatiu si de numarul de table de sah de dimensiune maxima.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 6$
* $1 ≤ N ≤ 2000$
* Fisierul de intrare va avea maxim $16$ MB.

h2. Exemplu
table(example). |_. tsah.in |_. tsah.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|1
5
00101
11010
00101
01010
11101
|3 3

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="tsah") ==

2177