पायथन में कॉलम स्वैपिंग की अनुमति के साथ 1 का सबसे बड़ा आयत खोजें

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है, हमें उस दिए गए मैट्रिक्स में सभी 1 का सबसे बड़ा आयत ढूंढना है। आयत को उस मैट्रिक्स के कॉलम के किसी भी जोड़े को स्वैप या एक्सचेंज करके बनाया जा सकता है।

तो, यदि इनपुट इस तरह है:

तो आउटपुट इस मामले में 6 होगा। आयत कॉलम 1 को 3 के साथ एक्सचेंज करके बनाया जा सकता है। एक्सचेंज के बाद मैट्रिक्स होगा:

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

• row := mat का आकार

• col := mat[0] का आकार

• temp := (row+1) x (col+1) क्रम का एक मैट्रिक्स, और 0 से भरा हुआ

• i को 0 से col तक के लिए, करें:

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

  • j को 1 से row तक के लिए, करें:

    • यदि mat[j, i], 0 के समान है, तो:

      • temp[j, i] := 0

    • अन्यथा,

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

• i को 0 से row तक के लिए, करें:

  • cnt := आकार (row+1) का एक ऐरे, और 0 से भरा हुआ

  • j को 0 से col तक, 1 से बढ़ाकर, करें:

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

  • col_no := 0

  • j := row

  • जब j >= 0, करें:

    • यदि cnt[j] > 0, तो:

      • k को 0 से cnt[j] तक के लिए, करें:

        • temp[i, col_no] := j

        • col_no := col_no + 1

    • j := j - 1

• area_maximum := 0

• i को 0 से row तक के लिए, करें:

  • j को 0 से col तक के लिए, करें:

    • 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