पायथन में मैट्रिक्स में सबसे बड़े द्वीप का क्षेत्रफल खोजने का प्रोग्राम

मान लीजिए हमारे पास एक बाइनरी मैट्रिक्स है। यहां 1 भूमि दर्शाता है और 0 पानी, और एक द्वीप 1s का एक समूह है जो पड़ोसी हैं जिनकी परिधि पानी से घिरी है। हम मान सकते हैं कि मैट्रिक्स के किनारे पानी से घिरे हैं। हमें मैट्रिक्स में सबसे बड़े द्वीप का क्षेत्रफल ढूंढना है।

उदाहरण के लिए, यदि इनपुट है:

तो आउटपुट 6 होगा।

समाधान दृष्टिकोण

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

• एक फंक्शन dfs() परिभाषित करें जो matrix, r, c लेता है:
  • total += 1
  • matrix[r][c] = 0 (देखा गया मार्क करें)
  • चारों दिशाओं (ऊपर, नीचे, बाएं, दाएं) के लिए:
    • यदि वैध और 1 है: dfs कॉल करें
• मुख्य मेथड से:
  • r_len, c_len आयाम
  • max_island := 0
  • प्रत्येक सेल के लिए:
    • यदि 1 है: total=0, dfs कॉल करें, max_island अपडेट करें
  • max_island लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, matrix):
        self.r_len = len(matrix)
        self.c_len = len(matrix[0])
        max_island = 0
        for r in range(self.r_len):
            for c in range(self.c_len):
                if matrix[r][c] == 1:
                    self.total = 0
                    self.dfs(matrix, r, c)
                    max_island = max(max_island, self.total)
        return max_island

    def dfs(self, matrix, r, c):
        self.total += 1
        matrix[r][c] = 0
        if r-1 >= 0 and matrix[r-1][c] == 1:
            self.dfs(matrix, r-1, c)
        if c-1 >= 0 and matrix[r][c-1] == 1:
            self.dfs(matrix, r, c-1)
        if r+1 < self.r_len and matrix[r+1][c] == 1:
            self.dfs(matrix, r+1, c)
        if c+1 < self.c_len and matrix[r][c+1] == 1:
            self.dfs(matrix, r, c+1)

ob = Solution()
matrix = [
    [0,0,1,1,1,1,1],
    [0,0,0,0,0,0,0],
    [0,1,1,1,1,0,0],
    [0,0,1,1,0,0,0],
    [0,0,0,0,0,1,1],
    [0,0,0,0,0,1,0]
]
print(ob.solve(matrix))

इनपुट

matrix = [[0,0,1,1,1,1,1],[0,0,0,0,0,0,0],[0,1,1,1,1,0,0],[0,0,1,1,0,0,0],[0,0,0,0,0,1,1],[0,0,0,0,0,1,0]]

आउटपुट

6