ম্যাট্রিক্সের কিছু উপাদান পরীক্ষা করার প্রোগ্রাম একটি চক্র গঠন করে নাকি পাইথনে নয়

ধরুন আমাদের একটি 2d ​​ম্যাট্রিক্স আছে। আমাদের পরীক্ষা করতে হবে যে আমরা কিছু সেল থেকে শুরু করতে পারি কিনা তারপর একই মানের সংলগ্ন কোষগুলিকে (উপর, নীচে, বাম, ডান) সরাতে পারি এবং একই প্রারম্ভিক বিন্দুতে ফিরে আসতে পারি। আমরা সর্বশেষ পরিদর্শন করেছি এমন একটি কক্ষে আমরা পুনরায় যেতে পারি না৷

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে True, যেহেতু আমরা একটি চক্র গঠন করতে 2s অনুসরণ করতে পারি।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• R :=ম্যাট্রিক্সের সারি গণনা
• C :=ম্যাট্রিক্সের কলাম সংখ্যা
• vis:=R x C আকারের একটি ম্যাট্রিক্স তৈরি করুন এবং False দিয়ে পূরণ করুন
• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি রুট নেবে
• স্ট্যাক :=দুটি উপাদান রুট এবং নাল সহ একটি স্ট্যাক
• vis[root[0], root[1]] :=সত্য
• স্ট্যাক খালি না থাকার সময়, করুন
  • [v, prev] :=স্ট্যাকের শীর্ষ উপাদান, এবং স্ট্যাক থেকে পপ
  • v এর প্রতিটি প্রতিবেশীর জন্য, করুন
    • যদি w আগের মত না হয়, তাহলে
      • যদি vis[w[0], w[1]] মিথ্যা হয়, তাহলে
        • দর্শন[w[0], w[1]] :=সত্য
        • স্ট্যাকের মধ্যে [w, v] পুশ করুন
    • অন্যথায়,
      • সত্য ফেরান
• মিথ্যে ফেরত দিন
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
• আমি 0 থেকে R - 1 রেঞ্জের জন্য, কর
  0 থেকে C - 1 এর মধ্যে j-এর জন্য
  • করুন
    • যদি 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