Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | tsah.in, tsah.out | Sursă | Selectie echipe ACM ICPC, UPB 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.175 sec | Limită de memorie | 5096 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Tsah
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.
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).
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'.
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.
Restrictii
- 1 ≤ T ≤ 6
- 1 ≤ N ≤ 2000
- Fisierul de intrare va avea maxim 16 MB.
Exemplu
| tsah.in | tsah.out |
|---|---|
| 1 5 00101 11010 00101 01010 11101 | 3 3 |
