|
|
| Line 1: |
Line 1: |
| == 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)'''.
| |
