Editing 3766 - Zid (section)

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

<code>2 3 5</code>

<code>2 2 3</code>

<code>5 5 3</code>

El conține <code>9</code> cărămizi, în care apar culorile <code>2</code>, <code>3</code>, <code>5</code> de câte <code>3</code> 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 <code>9</code> cărămizi, de exemplu:

<code>1 2 3</code>

<code>3 3 1</code>

<code>2 1 2</code>

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

<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>