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

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

इसलिए, यदि इनपुट इस प्रकार है:

1	0	1
0	0	0
1	1	0
1	1	1

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

हल करने के चरण

R := mat की पंक्तियों की संख्या, C := mat के स्तंभों की संख्या
mass := एक नया मैप
id := 555
floodfill() फ़ंक्शन परिभाषित करें। यह r, c, id लेगा
- यदि r और c मैट्रिक्स की रेंज में हैं और mat[r, c] 1 है, तो
  - mat[r, c] := id
  - mass[id] := mass[id] + 1
  - प्रत्येक जोड़ी (r2, c2) के लिए [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)] में, करें
    - floodfill(r2, c2, id)

मुख्य विधि से निम्नलिखित करें:

r के लिए 0 से R तक की रेंज में, करें
- c के लिए 0 से C तक की रेंज में, करें
  - यदि mat[r, c], 1 के समान है, तो
    - id := id + 1
    - mass[id] := 0
    - floodfill(r, c, id)
ans := (mass के सभी मान और 1) का अधिकतम

r के लिए 0 से R - 1 तक की रेंज में, करें

c के लिए 0 से C - 1 तक की रेंज में, करें
- यदि mat[r, c], 0 के समान नहीं है, तो अगले इटरेशन पर जाएं
- island_set := एक नया सेट
- प्रत्येक जोड़ी (r2, c2) के लिए [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)] में, करें
  - यदि r2 और c2, mat की रेंज में हैं और mat[r2, c2] 1 है, तो
    - mat[r2, c2] को island_set में जोड़ें
  - ans := ans और (1 + island_set में प्रत्येक island के लिए mass[island] का योग) का अधिकतम
ans लौटाएं

उदाहरण

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] = mass.get(id, 0) + 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]]