पायथन में दो मानचित्रों में अतिव्यापी द्वीपों की संख्या गिनने का कार्यक्रम

मान लीजिए कि हमारे पास दो बाइनरी मैट्रिक्स हैं mat1 तथा mat2। यहां 1 भूमि का प्रतिनिधित्व करता है और 0 पानी का प्रतिनिधित्व करता है, यदि पानी से घिरे 1 (भूमि) का समूह द्वीप कहलाता है। हमें एक ही निर्देशांक पर mat1 और mat2 दोनों में मौजूद द्वीपों की संख्या ज्ञात करनी है।

तो, अगर इनपुट mat1 की तरह है =

और मैट2 =

तो आउटपुट 2 होगा, क्योंकि अतिव्यापी द्वीप हैं,

इसलिए दो अतिव्यापी द्वीप हैं।

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

• r :=mat1 की पंक्ति गणना
• c :=mat1 की कॉलम संख्या
• last_row :=r - 1
• last_col :=c - 1
• एक फ़ंक्शन चिह्न () को परिभाषित करें। यह ले जाएगा मैं, जे
• mat1[i, j] :=0
• mat2[i, j] :=0
• यदि i शून्य नहीं है और (mat1[i-1, j] या mat2[i-1, j] कोई भी शून्य नहीं है), तो
  • चिह्नित करें(i-1, j)
• यदि j शून्य नहीं है और (mat1[i, j-1] या mat2[i, j-1] कोई भी शून्य नहीं है), तो
  • चिह्नित करें(i, j-1)
• अगर j
• चिह्नित करें(i, j + 1)

उदाहरण

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

def solve(mat1, mat2):
   r = len(mat1)
   c = len(mat1[0])
   last_row = r - 1
   last_col = c - 1

   def mark(i, j):
      mat1[i][j] = mat2[i][j] = 0
      if i and (mat1[i - 1][j] or mat2[i - 1][j]):
         mark(i - 1, j)
      if j and (mat1[i][j - 1] or mat2[i][j - 1]):
         mark(i, j - 1)
      if j < last_col and (mat1[i][j + 1] or mat2[i][j + 1]):
         mark(i, j + 1)
      if i < last_row and (mat1[i + 1][j] or mat2[i + 1][j]):
         mark(i + 1, j)

   for i in range(r):
      for j in range(c):
         if mat1[i][j] != mat2[i][j]:
            mark(i, j)

   islands = 0
   for i in range(r):
      for j in range(c):
         if mat1[i][j]:
            islands += 1
            mark(i, j)
   return islands

mat1 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 1]
]
mat2 = [
[1, 0, 1],
[1, 0, 0],
[1, 0, 0]
]
print(solve(mat1, mat2))

इनपुट

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

आउटपुट

2