1687 - Omogene

Enunț

Se consideră o matrice cu L linii și C coloane care memorează doar valori din mulțimea {0,1,2}. O submatrice nevidă (formată din cel puțin o linie și cel puțin o coloană) a acestei matrice o numim omogenă dacă numărul valorilor de 0 este egal cu numărul de valori de 1 și egal cu numărul valorilor de 2. De exemplu, în matricea

0 1 2 0
1 2 0 1
sunt șase submatrice omogene, acestea fiind:

0 1 2
1 2 0

1 2 0
2 0 1

0 1 2

1 2 0

1 2 0

2 0 1

Submatricele a treia și a patra sunt formate din prima linie a matricei inițială, iar submatricele a cincea și a șasea sunt formate din a doua linie.

Cerința

Să se determine câte submatrice nevide omogene există.

Date de intrare

Fișierul de intrare omogenein.txt conține pe prima linie numerele naturale L și C. Pe următoarele L linii se află câte C numere naturale separate prin spații reprezentând câte o linie din matrice.

Date de ieșire

Fișierul de ieșire omogeneout.txt va conține pe prima linie un singur număr natural reprezentând numărul submatricelor nevide omogene.

Restricții și precizări

• 2 ⩽ l ⩽ c ⩽ 500
• 4 ⩽ l*c ⩽ 65536
• Atenție, o submatrice este formată dintr-o secvență continuă de linii și coloane, deci, de exemplu, dacă se aleg dintr-o matrice liniile 1, 2 și 5, atunci acestea nu formează o submatrice.
• Numărul submatricelor omogene va fi mai mic decât 2*10^9
• Întreaga matrice poate fi submatrice omogenă

Exemplul 1

Intrare

omogenein.txt

2 4

0 1 2 0

1 2 0 1

Ieșire

Datele de intrare corespund restricțiilor impuse

omogeneout.txt

6

Explicație

Cele șase submatrice au fost menționate în enunț.

Exemplul 2

Intrare

omogenein.txt

3 3

0 1 2

0 2 2

0 1 1

Ieșire

Datele de intrare corespund restricțiilor impuse

omogeneout.txt

3

Exemplul 3

Intrare

omogenein.txt

1 3

0 1 2

0 2 2

0 1 1

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

#1687 - Omogene

def validare_date(l, c, matrice):
    if not (2 <= l <= c <= 5000):
        return False
    if not (4 <= l * c <= 65536):
        return False
    if len(matrice) != l or any(len(row) != c for row in matrice):
        return False
    return True


def numar_submatrici_omogene(l, c, matrice):
    if not validare_date(l, c, matrice):
        return 0

    numar_submatrici = 0

    for i in range(l):
        for j in range(c):
            for x in range(i, l):
                for y in range(j, c):
                    submatrice = [matrice[k][j:y + 1] for k in range(i, x + 1)]
                    numar_0 = sum(row.count(0) for row in submatrice)
                    numar_1 = sum(row.count(1) for row in submatrice)
                    numar_2 = sum(row.count(2) for row in submatrice)

                    if numar_0 == numar_1 == numar_2:
                        numar_submatrici += 1

    return numar_submatrici


with open("omogenein.txt", "r") as f:
    l, c = map(int, f.readline().split())
    matrice = [list(map(int, f.readline().split())) for _ in range(l)]

    if validare_date(l, c, matrice):
        print("Datele de intrare corespund restricțiilor impuse")

        rezultat = numar_submatrici_omogene(l, c, matrice)

        with open("omogeneout.txt", "w") as f:
            f.write(str(rezultat))

    else:
        print("Datele de intrare NU corespund restricțiilor impuse")
        exit(0)