इस समस्या में, हमें m X n आकार का एक वर्ग मैट्रिक्स मैट [] [] दिया जाता है जिसमें प्रत्येक तत्व 0 या 1 होता है। यदि किसी तत्व का मान 1 है, तो इसका मतलब है कि यह जुड़ा हुआ है, यदि मान 0 है, तो इसका मतलब यह है जुड़ा नहीं है। हमारा काम बाइनरी मैट्रिक्स में अधिकतम पथ लंबाई खोजना है।
समस्या का विवरण - समस्या को हल करने के लिए, हमें मैट्रिक्स पर सबसे बड़ा लंबाई पथ खोजने की जरूरत है, जिसका अर्थ है मैट्रिक्स में सभी 1 तत्व। पथ खोजने से पहले, हम अधिकतम एक को 0 से 1 में बदल देंगे।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
mat[][] = {{1, 0},
{0, 1}} आउटपुट
3
स्पष्टीकरण
We can convert 0 at index (0, 1) or (1, 0) to maximise the path length.
समाधान दृष्टिकोण
समस्या का एक सरल समाधान यह है कि प्रत्येक 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("The length of largest path is " + str(findLargestPath(I))) आउटपुट
The length of largest path is 3