3387 - Veverita
Cerinţa
Se dă o matrice cu n linii și m coloane cu valori de 0 și 1. Numim dreptunghi de extrem un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă.
Date de intrare
Fișierul de intrare colturi_drin.txt conține pe prima linie numărul n de linii, numărul m de coloane, iar pe următoarele linii se află cele n * m numere naturale.
Date de ieșire
Fișierul de ieșire colturi_dr.out va conține pe prima linie numerele nr, A si cnt reprezentând cele trei numere specificate în cerință.
Restricţii şi precizări
- 1 ⩽ n, m ⩽ 100
- numărul de dreptunghiuri de extrem cu vârfuri de 1 este diferit de numărul de dreptunghiuri de extrem cu vârfuri de 0.
- un dreptunghi de extrem are cel puțin două linii și două coloane
Exemplul 1
- colturi_drin.txt
5 5 1 0 1 0 1 1 1 1 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1
- colturi_dr.out
11 25 9
Rezolvare
<syntaxhighlight lang="python" line> def count_extreme_rectangles(matrix):
n = len(matrix) m = len(matrix[0]) cnt = [0, 0] max_area = [0, 0] max_area_cnt = [0, 0]
for i in range(n):
for j in range(m):
for k in range(i+1, n):
for o in range(j+1, m):
if matrix[i][j] == matrix[k][o] == matrix[i][o] == matrix[k][j]:
cnt[matrix[i][j]] += 1
area = (k-i+1) * (o-j+1)
if area > max_area[matrix[i][j]]:
max_area[matrix[i][j]] = area
max_area_cnt[matrix[i][j]] = 1
elif area == max_area[matrix[i][j]]:
max_area_cnt[matrix[i][j]] += 1
if max_area[0] > max_area[1]:
return cnt[0], max_area[0], max_area_cnt[0]
else:
return cnt[1], max_area[1], max_area_cnt[1]
def main():
n, m = map(int, input().split()) matrix = [list(map(int, input().split())) for _ in range(n)]
if n > 100 or m > 100:
print("Datele de intrare nu corespund restrictiilor impuse")
return
nr, A, cnt = count_extreme_rectangles(matrix)
print("Datele de intrare corespund restrictiilor impuse")
print(nr, A, cnt)
if __name__ == "__main__":
main()
</syntaxhighlight>
Explicatie
Sunt 9 dreptunghiuri de extrem a cărui vârfuri sunt 1, respectiv 2 ale cărui vârfuri sunt 0. Dreptunghiul de extrem de arie maximă are colțul stânga sus la (0,0) și colțul dreapta jos la (5,5).