पायथन में बाइनरी मैट्रिक्स में अधिकतम पथ लंबाई खोजें

इस समस्या में, हमें आकार m X n का एक वर्ग मैट्रिक्स mat[][] दिया जाता है जिसमें प्रत्येक एलिमेंट या तो 0 या 1 होता है। यदि किसी एलिमेंट का मान 1 है, तो इसका मतलब है कि यह जुड़ा हुआ है, यदि मान 0 है, तो इसका मतलब है कि यह जुड़ा हुआ नहीं है। हमारा कार्य बाइनरी मैट्रिक्स में अधिकतम पथ लंबाई खोजना है।

समस्या विवरण - समस्या को हल करने के लिए, हमें मैट्रिक्स पर सबसे बड़ी लंबाई का पथ खोजने की आवश्यकता है, जिसका अर्थ है मैट्रिक्स में सभी 1 एलिमेंट्स। पथ खोजने से पहले, हम अधिकतम एक 0 को 1 में बदलेंगे।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

mat[][] = {{1, 0}, {0, 1}}

आउटपुट

3

व्याख्या

हम इंडेक्स (0, 1) या (1, 0) पर 0 को 1 में बदलकर पथ लंबाई को अधिकतम कर सकते हैं।

समाधान दृष्टिकोण

समस्या का एक सरल समाधान प्रत्येक 0 को 1 में बदलने के बाद लंबाई खोजना है। हम पथ की लंबाई खोजने के लिए डेप्थ-फर्स्ट सर्च का उपयोग करेंगे और फिर सभी पथ लंबाई में से अधिकतम लौटाएंगे।

एक कुशल समाधान कई रूपांतरण करने की आवश्यकता को समाप्त करेगा और उस एक के लिए समझौता करेगा जो सबसे आशाजनक समाधान देता है। हम एक ऐसा समूह ढूंढेंगे जहां एक 0 को 1 में बदलने से सबसे बड़ी लंबाई का पथ वापस मिलेगा।

हमारे समाधान के काम को दिखाने वाला प्रोग्राम,

उदाहरण

def FindNeighbor(R, C, N):
    for nr, nc in (((R - 1), C), ((R + 1), C), (R, (C - 1)), (R, (C + 1))):
        if 0 <= nr < N and 0 <= nc < N:
            yield nr, nc

def DFSTraversal(R, C, index, mat, N):
    maxLen = 1
    mat[R][C] = index
    for nr, nc in FindNeighbor(R, C, N):
        if mat[nr][nc] == 1:
            maxLen += DFSTraversal(nr, nc, index)
    return maxLen

def findLargestPath(mat):
    N = len(mat)
    maxPath = {}
    index = 2
    for i in range(N):
        for j in range(N):
            if mat[i][j] == 1:
                maxPath[index] = DFSTraversal(i, j, index, mat, N)
                index += 1
    maxPathLen = max(maxPath.values() or [0])
    for i in range(N):
        for j in range(N):
            if mat[i][j] == 0:
                seen = {mat[nr][nc] for nr, nc in FindNeighbor(i, j, N) if mat[nr][nc] > 1}
                maxPathLen = max(maxPathLen, 1 + sum(maxPath[i] for i in seen))
    return maxPathLen

I = [[1, 0], [0, 1]]
print("सबसे बड़े पथ की लंबाई है " + str(findLargestPath(I)))

आउटपुट

सबसे बड़े पथ की लंबाई है 3