अजगर में मैट्रिक्स में घिरे द्वीपों की संख्या गिनने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी मैट्रिक्स है। जहां 1 भूमि का प्रतिनिधित्व करता है और 0 पानी का प्रतिनिधित्व करता है। जैसा कि हम जानते हैं कि एक द्वीप 1s का एक समूह है जो एक साथ समूहीकृत होता है जिसकी परिधि पानी से घिरी होती है। हमें पूरी तरह से घिरे हुए द्वीपों की संख्या ज्ञात करनी है।

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

तो आउटपुट 2 होगा, क्योंकि तीन द्वीप हैं, लेकिन उनमें से दो पूरी तरह से घिरे हुए हैं।

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

एक फ़ंक्शन को परिभाषित करें dfs() । यह ले जाएगा मैं, जे
यदि i और j मैट्रिक्स की सीमा में नहीं हैं, तो
- झूठी वापसी
यदि मैट्रिक्स [i, j] 0 के समान है, तो
- सही लौटें
मैट्रिक्स[i, j] :=0
a :=dfs(i + 1, j)
b :=dfs(i-1, j)
c :=dfs(i, j + 1)
d :=dfs(i, j-1)
ए और बी और सी और डी लौटाएं
मुख्य विधि से निम्न कार्य करें:
R:=मैट्रिक्स की पंक्ति गणना, C:=मैट्रिक्स की कॉलम गणना
उत्तर:=0
0 से R की श्रेणी में i के लिए, करें
- जे के लिए 0 से सी की सीमा में, करें
  - यदि मैट्रिक्स [i, j] 1 के समान है, तो
    - यदि dfs(i, j) सत्य है, तो
      - उत्तर:=उत्तर + 1
वापसी उत्तर

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

उदाहरण

class Solution:
   def solve(self, matrix):
      def dfs(i, j):
         if i < 0 or j < 0 or i >= R or j >= C:
            return False
         if matrix[i][j] == 0:
            return True
         matrix[i][j] = 0
         a = dfs(i + 1, j)
         b = dfs(i - 1, j)
         c = dfs(i, j + 1)
         d = dfs(i, j - 1)
         return a and b and c and d

      R, C = len(matrix), len(matrix[0])
      ans = 0
      for i in range(R):
         for j in range(C):
            if matrix[i][j] == 1:
               if dfs(i, j):
                  ans += 1
      return ans

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

इनपुट

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