Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-08 21:19:05.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:tsah.in, tsah.outSursăSelectie echipe ACM ICPC, UPB 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.175 secLimită de memorie5096 kbytes
Scorul tăuN/ADificultateN/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 ≤ N ≤ 2000

Exemplu

tsah.intsah.out
1
5
00101
11010
00101
01010
11101
3 3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?