이진 행렬이 있다고 가정하면 해당 행렬에서 모든 1 중 가장 큰 직사각형을 찾아야 합니다. 사각형은 해당 행렬의 열 쌍을 바꾸거나 교환하여 만들 수 있습니다.
따라서 입력이 다음과 같으면
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
이 경우 출력은 6이 됩니다. 사각형은 열 1을 3으로 교환하여 생성할 수 있습니다. 교환 후 행렬은 -
| 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 |
이 문제를 해결하기 위해 다음 단계를 따릅니다.
-
row :=매트의 크기
-
col :=매트의 크기[0]
-
temp :=순서(행 + 1) x (열 + 1)의 행렬, 0으로 채움
-
범위 0에서 col까지의 i에 대해 수행
-
temp[0, i] :=매트[0, i]
-
행까지 범위 1의 j에 대해 수행
-
mat[j, i]가 0과 같으면
-
temp[j, i] :=0
-
-
그렇지 않으면
-
temp[j, i] :=temp[j - 1, i] + 1
-
-
-
-
범위 0에서 행까지의 i에 대해 수행
-
cnt :=크기의 배열(행 + 1), 0으로 채워짐
-
범위 0에서 열까지의 j에 대해 1씩 증가, 수행
-
cnt[temp[i,j]] :=cnt[temp[i,j]] + 1
-
-
col_no :=0
-
j :=행
-
j>=0인 동안 수행
-
cnt[j]> 0이면
-
범위 0에서 cnt[j]에 있는 k에 대해 수행
-
temp[i, col_no] :=j
-
col_no :=col_no + 1
-
-
-
j :=j - 1
-
-
-
area_maximum :=0
-
범위 0에서 행까지의 i에 대해 수행
-
0에서 col 범위의 j에 대해 수행
-
area_current :=(j + 1) * temp[i, j]
-
area_current> area_maximum이면
-
area_maximum :=area_current
-
-
-
-
반환 area_maximum
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def maxArea(mat):
row = len(mat)
col = len(mat[0])
temp = [[0 for i in range(col + 1)] for i in range(row + 1)]
for i in range(0, col):
temp[0][i] = mat[0][i]
for j in range(1, row):
if ((mat[j][i] == 0)):
temp[j][i] = 0
else:
temp[j][i] = temp[j - 1][i] + 1
for i in range(0, row):
cnt = [0 for i in range(row + 1)]
for j in range(0, col, 1):
cnt[temp[i][j]] += 1
col_no = 0
j = row
while(j >= 0):
if (cnt[j] > 0):
for k in range(0, cnt[j]):
temp[i][col_no] = j
col_no += 1
j -= 1
area_maximum = 0
for i in range(0, row):
for j in range(0, col):
area_current = (j + 1) * temp[i][j]
if (area_current > area_maximum):
area_maximum = area_current
return area_maximum
mat = [
[0, 0, 1, 1, 0],
[0, 0, 1, 1, 1],
[1, 0, 1, 1, 0]]
print("Area : ",maxArea(mat)) 입력
[ [1, 0, 0, 1, 0], [1, 0, 0, 1, 1], [1, 1, 0, 1, 0]]
출력
Area : 2