2429 - matrice9

Cerinta

Se cere să se găsească o submatrice validă a lui A de arie maximă.

Date de intrare

Fișierul de intrare matrice9.in conține pe prima linie numerele N şi M, separate prin spaţiu. Pe fiecare dintre următoarele N linii se află câte M numere întregi separate prin câte un spaţiu, reprezentând elementele matricei A.

Date de iesire

Fișierul de ieșire matrice9.out va conţine o singură linie pe care vor fi scrise coordonatele l1, c1, l2, c2 (în această ordine şi separate prin câte un spaţiu) ale unei submatrice valide de arie maximă. În cazul în care există mai multe soluţii cu arie maximă, se va afişa oricare dintre ele.

Restrictii si precizari

1 ≤ N, M ≤ 1000
70% din teste vor avea N, M ≤ 600
Elementele matricei A sunt numere întregi din intervalul [-30000, 30000].

Exemplul 1

intrare

2 6

1 2 5 7 9 10

3 4 3 5 1 10

iesire

Datele introduse corespund restrictiilor impuse.

1 1 2 3

Exemplul 2

intrare

3 7

2 3 6 8 10 11

4 5 4 6 2 11

iesire

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

2429 - matrice9

def este_sir_valid(sir):

   # Verifică dacă un șir este valid conform definiției date
   # Puteți implementa această funcție în funcție de specificațiile exacte ale problemei

def este_submatrice_valida(matrice, l1, c1, l2, c2):

   # Verifică dacă o submatrice este validă conform definiției date
   # Parcurge liniile submatricei și verifică dacă fiecare linie este un șir valid
   for i in range(l1, l2 + 1):
       linie_submatrice = matrice[i][c1:c2 + 1]
       if not este_sir_valid(linie_submatrice):
           return False
   return True

def calculeaza_aria_submatrice(matrice, l1, c1, l2, c2):

   # Calculează aria unei submatrice
   return (l2 - l1 + 1) * (c2 - c1 + 1)

def gaseste_submatrice_maxima(matrice):

   # Găsește și returnează submatricea de dimensiuni maxime care este validă
   max_aria = 0
   coordonate_maxime = None

   for l1 in range(len(matrice)):
       for c1 in range(len(matrice[0])):
           for l2 in range(l1, len(matrice)):
               for c2 in range(c1, len(matrice[0])):
                   if este_submatrice_valida(matrice, l1, c1, l2, c2):
                       aria = calculeaza_aria_submatrice(matrice, l1, c1, l2, c2)
                       if aria > max_aria:
                           max_aria = aria
                           coordonate_maxime = (l1, c1, l2, c2)

   return coordonate_maxime