Fişierul intrare/ieşire:poze.in, poze.outSursăLot Alba 2006
AutorCosmin Silvestru NegruseriAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.5 secLimită de memorie36096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Poze

Ciobanasul Ion a devenit pasionat de fotografierea peisajelor din jurul stanei lui si mai nou, dupa cumpararea unui calculator, este pasionat si de prelucrarea acestor imagini.

Acum, Ion are un set de T poze, numerotate de la 1 la T. Ion a codificat fiecare poza ca matrice dreptunghiulara de numere naturale, in care retine culoarea fiecarui pixel din poza.

Pentru fiecare poza, Ion analizeaza zone de forma patrata si observa ca modelul din anumite zone apare in poza de mai multe ori. Aparitiile pe care el le observa nu sunt neaparat disjuncte, ele se pot suprapune partial.

Acum Ion vrea sa determine pentru fiecare poza i lungimea maxima a laturii unei zone patrate al carei model apare in poza i de cel putin Ki ori, fara rotatii. Lungimea laturii unei zone patrate este egala cu numarul de linii (acelasi cu numarul de coloane) ale zonei.

Cerinta

Scrieti un program care sa determine pentru fiecare poza i din set lungimea maxima a laturii unei zone de forma patrata al carei model apare in poza de cel putin Ki ori.

Date de intrare

Fisierul poze.in va contine pe prima linie un numar intreg T, reprezentand numarul de poze. In urmatoarele linii ale fisierului se vor afla descrierile celor T poze. Descrierea unei poze va incepe cu o linie ce contine trei numere naturale N M K, separate prin cate un spatiu, unde N reprezinta numarul de linii ale matricei, M numarul de coloane ale matricei, iar K numarul minim dorit de aparitii ale zonei patrate. Urmatoarele N linii vor contine cate M numere naturale separate prin spatii ce reprezinta culorile pixelilor pozei.

Date de iesire

Fisierul poze.out va contine exact T linii. Linia i va contine un intreg reprezentand lungimea maxima a laturii unei zone patrate ce apare in poza i de cel putin Ki ori.

Restrictii

  • 1 ≤ T ≤ 5
  • 1 ≤ N, M ≤ 300
  • 2 ≤ Ki ≤ 5
  • Culorile pixelilor sunt numere naturale ≤ 30000

Exemplu

poze.inpoze.out
3
4 4 2
0 0 1 0
0 0 1 0
1 1 0 1
1 1 0 0
3 3 2
3 0 1
0 3 0
1 0 3
3 3 5
0 0 1
0 0 1
1 1 2
2
2
0

Explicatie

Pentru prima poza, modelul din zona patratica de latura 2 cu coltul stanga-sus in pozitia (1, 3) apare de doua ori.

Pentru cea de a doua poza, modelul din zona patratica de latura 2 cu coltul stanga-sus in pozitia (1, 1) apare de doua ori.

Pentru cea de a treia poza, nu exista nici o zona patratica al carei model sa apara de cel putin 5 ori, deci lungimea maxima a laturii este 0.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content