पायथन में एक जल कोशिका को भूमि कोशिका में बदलने के बाद सबसे बड़ा द्वीप खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक द्विआधारी मैट्रिक्स है जहां 1 भूमि का प्रतिनिधित्व करता है और 0 पानी का प्रतिनिधित्व करता है। और एक द्वीप 1s का एक समूह है जो पानी से घिरा हुआ है। हमें सबसे बड़े द्वीप के आकार का पता लगाना है। हमें ज़्यादा से ज़्यादा एक वॉटर सेल को लैंड सेल में बदलने की अनुमति है।

तो, अगर इनपुट पसंद है

तो उत्पादन 7 होगा, क्योंकि हम दो द्वीपों को जोड़ने के लिए एक जल कोशिकाओं को जमीन पर ले जा सकते हैं। तो अंतिम मैट्रिक्स इस तरह है -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• आर:=चटाई की पंक्ति संख्या, सी:=चटाई की स्तंभ संख्या

• द्रव्यमान:=एक नया नक्शा

• आईडी:=555

• फ्लडफिल () फ़ंक्शन को परिभाषित करें। इसमें r, c, id लगेगा

• यदि r और c मैट्रिक्स की श्रेणी में हैं और mat[r, c] 1 है, तो

  • चटाई[आर, सी] :=आईडी

  • द्रव्यमान [आईडी]:=द्रव्यमान [आईडी] + 1

  • [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1)] में प्रत्येक जोड़ी (r2, c2) के लिए, करें

    • फ्लडफिल(r2, c2, id)

• मुख्य विधि से निम्न कार्य करें -

• r के लिए 0 से R की सीमा में, करें

  • सी के लिए 0 से सी की सीमा में, करें

    • अगर मैट [आर, सी] 1 के समान है, तो

      • आईडी:=आईडी + 1

      • मास [आईडी] :=0

      • फ्लडफिल (आर, सी, आईडी)

• उत्तर :=अधिकतम (द्रव्यमान के सभी मान और 1)

• r के लिए 0 से R − 1 की सीमा में, करें

  • सी के लिए 0 से सी -1 की सीमा में, करो

    • अगर मैट [आर, सी] 0 के समान नहीं है, तो

      • अगले पुनरावृत्ति के लिए जाएं

    • Island_set :=एक नया सेट

    • [(r + 1, c) ,(r − 1, c) ,(r, c + 1) ,(r, c − 1)] में प्रत्येक जोड़ी (r2, c2) के लिए, करें

      • अगर r2 और c2 चटाई की सीमा में हैं और चटाई [r2, c2] 1 है, तो

        • द्वीप_सेट में मैट [r2, c2] जोड़ें

      • उत्तर :=अधिकतम उत्तर और (प्रत्येक द्वीप inisland_set के लिए सभी द्रव्यमान [द्वीप] का 1 + योग)

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
   def solve(self, mat):
      R, C = len(mat), len(mat[0])
      mass = {}
      id = 555
      def floodfill(r, c, id):
         nonlocal R, C, mat, mass
         if 0 <= r < R and 0 <= c < C and mat[r][c] == 1:
            mat[r][c] = id
            mass[id] += 1
            for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),
               (r, c − 1)]:
               floodfill(r2, c2, id)
                  for r in range(R):
      for c in range(C):
         if mat[r][c] == 1:
            id += 1
            mass[id] = 0
            floodfill(r, c, id)
      ans = max([val for val in mass.values()] + [1])
      for r in range(R):
         for c in range(C):
            if mat[r][c] != 0:
               continue
            island_set = set()
            for r2, c2 in [(r + 1, c), (r − 1, c), (r, c + 1),(r, c − 1)]:
               if 0 <= r2 < R and 0 <= c2 < C and mat[r2][c2]:
                  island_set.add(mat[r2][c2])
               ans = max(ans, 1 + sum([mass[island] for island in island_set]))
         return ans
ob = Solution()
matrix = [
   [1, 0, 1],
   [0, 0, 0],
   [1, 1, 0],
   [1, 1, 1]
]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

7