Python में मैट्रिक्स के कुछ तत्व साइकिल बनाते हैं या नहीं, इसकी जांच करने का प्रोग्राम

मान लीजिए हमारे पास एक 2D मैट्रिक्स है। हमें जांचना है कि क्या हम किसी सेल से शुरू करके समान मान वाले आसन्न सेल (ऊपर, नीचे, बाएं, दाएं) पर जा सकते हैं, और उसी शुरुआती बिंदु पर वापस आ सकते हैं। हम उस सेल को दोबारा नहीं देख सकते जिसे हमने अंतिम बार देखा था।

इसलिए, यदि इनपुट इस तरह है

तो आउटपुट True होगा, क्योंकि हम 2 का पालन करके एक साइकिल बना सकते हैं।

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

• R := मैट्रिक्स की पंक्ति संख्या
• C := मैट्रिक्स की कॉलम संख्या
• vis := R x C आकार का मैट्रिक्स बनाएं और False से भरें
• dfs() फ़ंक्शन परिभाषित करें। यह रूट लेगा
• stack := रूट और null दो तत्वों वाला एक स्टैक
• vis[root[0], root[1]] := True
• जब तक स्टैक खाली नहीं है, करें
  • [v, prev] := स्टैक का शीर्ष तत्व, और स्टैक से पॉप करें
  • v के प्रत्येक पड़ोसी w के लिए, करें
    • यदि w prev के समान नहीं है, तो
      • यदि vis[w[0], w[1]] गलत है, तो
        • vis[w[0], w[1]] := True
        • [w, v] को स्टैक में पुश करें
    • अन्यथा,
      • True लौटाएं
• False लौटाएं
• मुख्य मेथड से निम्नलिखित करें:
• i को 0 से R-1 तक रेंज में, करें
  • j को 0 से C-1 तक रेंज में, करें
    • यदि vis[i, j] गलत है, तो
      • यदि dfs((i, j)) सत्य है, तो
        • True लौटाएं
• False लौटाएं

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

उदाहरण

class Solution:
    def solve(self, matrix):
        R = len(matrix)
        C = len(matrix[0])
        def get_neighbors(i, j):
            val = matrix[i][j]
            for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == val:
                    yield ii, jj
        vis = [[False] * C for _ in range(R)]
        def dfs(root):
            stack = [(root, None)]
            vis[root[0]][root[1]] = True
            while stack:
                v, prev = stack.pop()
                for w in get_neighbors(*v):
                    if w != prev:
                        if not vis[w[0]][w[1]]:
                            vis[w[0]][w[1]] = True
                            stack.append((w, v))
                        else:
                            return True
            return False
        for i in range(R):
            for j in range(C):
                if not vis[i][j]:
                    if dfs((i, j)):
                        return True
        return False
ob = Solution()
matrix = [
    [2, 2, 2, 1],
    [2, 1, 2, 1],
    [2, 2, 2, 1]
]
print(ob.solve(matrix))

इनपुट

[ [2, 2, 2, 1], [2, 1, 2, 1], [2, 2, 2, 1] ]

आउटपुट

True