Python में दो मैप्स में ओवरलैपिंग द्वीपों की संख्या गिनने का प्रोग्राम

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

इसलिए, यदि इनपुट है mat1 = [[1,0,1],[1,0,0],[1,0,0]] और mat2 = [[1,0,1],[1,0,0],[1,0,1]] तो आउटपुट 2 होगा, क्योंकि ओवरलैपिंग द्वीप हैं:

हल करने का दृष्टिकोण

r := mat1 की पंक्ति संख्या
c := mat1 की स्तंभ संख्या
last_row := r - 1
last_col := c - 1
mark() फ़ंक्शन परिभाषित करें। यह i, j लेगा
mat1[i, j] := 0
mat2[i, j] := 0
यदि i शून्येतर है और (mat1[i-1, j] या mat2[i-1, j] में से कोई शून्येतर है), तो mark(i-1, j)
यदि j शून्येतर है और (mat1[i, j-1] या mat2[i, j-1] में से कोई शून्येतर है), तो mark(i, j-1)
यदि j < last_col और (mat1[i, j+1] या mat2[i, j+1] में से कोई शून्येतर है), तो mark(i, j+1)
यदि i < last_row और (mat1[i+1, j] या mat2[i+1, j] में से कोई शून्येतर है), तो mark(i+1, j)
मुख्य विधि से, 0 से r-1 तक i के लिए, 0 से c-1 तक j के लिए, यदि mat1[i, j] mat2[i, j] के समान नहीं है, तो mark(i, j)
islands := 0
0 से r-1 तक i के लिए, 0 से c-1 तक j के लिए, यदि mat1[i, j] शून्येतर है, तो islands बढ़ाएं और mark(i, j)
islands लौटाएं

उदाहरण

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]]