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

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

तो, अगर इनपुट पसंद है

तब आउटपुट सही होगा, क्योंकि हम एक चक्र बनाने के लिए 2s का अनुसरण कर सकते हैं।

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

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

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

उदाहरण

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