Tìm hình chữ nhật lớn nhất trong số 1 của với việc hoán đổi các cột được phép trong Python

Giả sử chúng ta có một ma trận nhị phân, chúng ta phải tìm hình chữ nhật lớn nhất trong tất cả các số 1 trong ma trận đã cho đó. Hình chữ nhật có thể được tạo bằng cách hoán đổi hoặc hoán đổi bất kỳ cặp cột nào của ma trận đó.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 6 trong trường hợp này. Hình chữ nhật có thể được tạo ra bằng cách trao đổi cột 1 với 3. Ma trận sau khi trao đổi sẽ là -

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• row:=kích thước của tấm thảm

• col:=kích thước của tấm thảm [0]

• temp:=ma trận có thứ tự (hàng + 1) x (cột + 1) và điền bằng 0

• đối với tôi trong phạm vi 0 đến col, do

  • temp [0, i]:=mat [0, i]

  • đối với j trong phạm vi từ 1 đến hàng, thực hiện

    • nếu mat [j, i] giống 0 thì

      • tạm thời [j, i]:=0

    • nếu không,

      • temp [j, i]:=temp [j - 1, i] + 1

• đối với tôi trong phạm vi từ 0 đến hàng, hãy thực hiện

  • cnt:=một mảng có kích thước (hàng + 1) và được điền bằng 0

  • cho j trong phạm vi 0 đến col, tăng 1, làm

    • cnt [temp [i, j]]:=cnt [temp [i, j]] + 1

  • col_no:=0

  • j:=hàng

  • while j> =0, do

    • nếu cnt [j]> 0, thì

      • đối với k trong phạm vi 0 đến cnt [j], thực hiện

        • temp [i, col_no]:=j

        • col_no:=col_no + 1

    • j:=j - 1

• area_maximum:=0

• đối với tôi trong phạm vi từ 0 đến hàng, hãy thực hiện

  • đối với j trong phạm vi 0 đến col, do

    • area_current:=(j + 1) * temp [i, j]

    • nếu area_current> area_maximum, thì

      • area_maximum:=area_current

• return area_maximum

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[ [1, 0, 0, 1, 0],
[1, 0, 0, 1, 1],
[1, 1, 0, 1, 0]]

Đầu ra

Area : 2