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

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

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

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

हल करने के चरण

• dfs() फ़ंक्शन परिभाषित करें। यह i, j, k, l लेगा

  • mat[i, j] := 0

  • पेयर (i - k, j - l) को shape के अंत में डालें

  • यदि i + 1 < mat की पंक्तियों की संख्या और mat[i + 1, j] 1 है, तो dfs(i + 1, j, k, l)

  • यदि j + 1 < mat के स्तंभों की संख्या और mat[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)

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

  • cnt := 0

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

  • i के लिए 0 से mat की पंक्तियों की संख्या तक की रेंज में, करें

    • j के लिए 0 से mat के स्तंभों की संख्या तक की रेंज में, करें

      • यदि mat[i, j] 1 है, तो

        • shape := एक नई सूची

        • dfs(i, j, i, j)

        • यदि shape, shapes में नहीं है, तो cnt := cnt + 1

        • shape को shapes में डालें

  • cnt लौटाएं

  उदाहरण

  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