पायथन में दिए गए मैट्रिक्स से अलग-अलग द्वीप आकृतियों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास 2d बाइनरी मैट्रिक्स है, हमें दिए गए मैट्रिक्स में अलग-अलग द्वीपों की संख्या ज्ञात करनी है। यहां 1 भूमि का प्रतिनिधित्व करता है और 0 पानी का प्रतिनिधित्व करता है, इसलिए एक द्वीप 1 का एक समूह है जो करीब है और जिसकी परिधि पानी से घिरी हुई है। यहां दो द्वीप अद्वितीय हैं यदि उनके आकार अलग हैं।

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

तो आउटपुट 4 होगा (अलग द्वीप अलग-अलग रंगों में हैं)।

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

• फ़ंक्शन को परिभाषित करें dfs() । इसमें i, j, k, l

  . लगेगा

• चटाई[i, j] :=0

• आकृति के अंत में जोड़ी (i - k, j - l) डालें

• अगर i + 1 <चटाई और चटाई की पंक्ति संख्या [i + 1, j] 1 है, तो

  • dfs(i + 1, j, k, l)

• अगर j + 1 <चटाई और चटाई की कॉलम संख्या [i, j + 1] 1 है, तो

  • dfs(i, j + 1, k, l)

• अगर i − 1>=0 और mat[i − 1, j] 1 है, तो

  • dfs(i − 1, j, k, l)

• अगर j − 1>=0 और mat[i, j − 1] 1 है, तो

  • dfs(i, j − 1, k, l)

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

• सीएनटी:=0

• आकार :=एक नया सेट

• मैं के लिए 0 से लेकर पंक्ति तक चटाई की गिनती में, करें

  • j के लिए रेंज 0 से लेकर मैट की कॉलम काउंट तक, करें

    • अगर मैट [i, j] 1 है, तो

      • आकार :=एक नई सूची

      • dfs(i, j, i, j)

      • अगर आकार आकार में नहीं है, तो

        • सीएनटी:=सीएनटी + 1

      • आकृतियों में आकार डालें

• वापसी सीएनटी

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

उदाहरण

class Solution:
   def solve(self, mat):
      def dfs(i, j, k, l):
         mat[i][j] = 0
         shape.append((i − k, j − l))
      if i + 1 < len(mat) and mat[i + 1][j]:
         dfs(i + 1, j, k, l)
      if j + 1 < len(mat[0]) and mat[i][j + 1]:
         dfs(i, j + 1, k, l)
      if i − 1 >= 0 and mat[i − 1][j]:
         dfs(i − 1, j, k, l)
      if j − 1 >= 0 and mat[i][j − 1]:
         dfs(i, j − 1, k, l)
   cnt = 0
   shapes = set()
      for i in range(len(mat)):
         for j in range(len(mat[0])):
            if mat[i][j]:
               shape = []
               dfs(i, j, i, j)
               shape = tuple(shape)
               if shape not in shapes:
                  cnt += 1
                  shapes.add(shape)
      return cnt
ob = Solution()
matrix = [
   [1, 0, 0, 0, 0],
   [1, 0, 1, 0, 1],
   [0, 1, 1, 0, 1],
   [0, 0, 1, 0, 0],
   [1, 0, 0, 0, 0],
   [1, 1, 0, 1, 1]
]
print(ob.solve(matrix))

इनपुट

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

आउटपुट

4