3766 - Zid

Un zid ornamental de formă dreptunghiulară este alcătuit din N rânduri de cărămizi, fiecare rând având câte M cărămizi identice, așezate una lângă alta. Fiecare cărămidă este colorată într-una dintre culorile {0, 1, 2, ..., Cmaxg}. Un pătrat de latură L în acest zid este constituit din cărămizile situate pe L rânduri consecutive și L coloane consecutive. Spunem că un pătrat este colorat uniform dacă el conține același număr de cărămizi din fiecare culoare care apare în pătratul respectiv.

Cerința

Scrieți un program care, cunoscând configurația zidului, determină în acest zid un pătrat de latură maximă, colorat uniform.

Date de intrare

Fișierul de intrare zid.in conține pe prima linie numerele naturale N M Cmax, reprezentând numărul de rânduri de cărămizi, numărul de cărămizi de pe fiecare rând, respectiv culoarea maximă. Pe următoarele N linii este descrisă configurația zidului, de sus în jos; pe fiecare linie dintre cele N se află câte M numere naturale, reprezentând culorile cărămizilor de pe rândul respectiv, în ordine, de la stânga la dreapta. Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire zid.out va conține o singură linie pe care vor fi scrise trei numere naturale Nr R C, separate prin câte un singur spațiu, reprezentând numărul de cărămizi existente într-un pătrat colorat uniform de latură maximă, respectiv rândul și cărămida de pe rând situată în colțul din stânga-sus al pătratului colorat uniform de latură maximă.

Restricții și precizări

• 2 ≤ N, M ≤ 250• 1 ≤ Cmax ≤ 9 • Rândurile sunt numerotate de sus în jos de la 1 la N. Cărămizile situate pe un rând sunt numerotate de la stânga la dreapta de la 1 la M. • Dacă există mai multe pătrate colorate uniform de latură maximă se va alege pătratul pentru care numărul rândului este minim. Dacă există mai multe pătrate colorate uniform de latură maximă care au colțul din stânga-sus pe același rând minim, se va alege pătratul cel mai din stânga.

Exemplu:

zid.in

6 8 5
1 2 3 5 1 2 3 5
1 2 1 2 3 5 3 5
1 1 1 2 2 3 3 3
1 2 3 5 5 3 2 1
3 3 1 1 2 2 5 5
2 1 2 3 2 5 2 2

zid.out

9 2 4

Explicație

Pătratul colorat uniform de latură maximă, situat pe rândul cel mai de sus, cel mai în stânga este:

2 3 5

2 2 3

5 5 3

El conține 9 cărămizi, în care apar culorile 2, 3, 5 de câte 3 ori fiecare. Acest pătrat are colțul din

stânga-sus situat pe rândul al doilea, în a patra cărămidă de pe rând (a patra coloană). Există și alte pătrate colorate uniform formate din 9 cărămizi, de exemplu:

1 2 3

3 3 1

2 1 2

dar acesta are colțul din stânga-sus pe rândul 4.

<syntaxhighlight lang="python" line="1"> def citire_date():

   N, M, Cmax = map(int, input().split())
   zid = [list(map(int, input().split())) for _ in range(N)]
   return N, M, Cmax, zid

def construieste_matrice_cumulative(N, M, Cmax, zid):

   cumulative = [[[0] * (Cmax + 1) for _ in range(M + 1)] for _ in range(N + 1)]
   
   for i in range(1, N + 1):
       for j in range(1, M + 1):
           culoare = zid[i-1][j-1]
           for c in range(Cmax + 1):
               cumulative[i][j][c] = cumulative[i-1][j][c] + cumulative[i][j-1][c] - cumulative[i-1][j-1][c]
           cumulative[i][j][culoare] += 1

   return cumulative

def verifica_uniformitatea(cumulative, x1, y1, x2, y2, Cmax):

   counts = [0] * (Cmax + 1)
   
   for c in range(Cmax + 1):
       counts[c] = (cumulative[x2][y2][c]
                    - cumulative[x1-1][y2][c]
                    - cumulative[x2][y1-1][c]
                    + cumulative[x1-1][y1-1][c])
   
   unique_counts = [count for count in counts if count > 0]
   return len(set(unique_counts)) == 1

def gaseste_patrat_maxim_uniform(N, M, Cmax, zid):

   cumulative = construieste_matrice_cumulative(N, M, Cmax, zid)
   
   latura_maxima = min(N, M)
   
   for latura in range(latura_maxima, 0, -1):
       for i in range(1, N - latura + 2):
           for j in range(1, M - latura + 2):
               if verifica_uniformitatea(cumulative, i, j, i + latura - 1, j + latura - 1, Cmax):
                   return latura
   
   return 0

def main():

   N, M, Cmax, zid = citire_date()
   latura_maxima = gaseste_patrat_maxim_uniform(N, M, Cmax, zid)
   print(latura_maxima)

if __name__ == "__main__":

   main()

</syntaxhighlight>