পাইথনে ম্যাট্রিক্সের কিছু এলিমেন্ট সাইকেল (cycle) তৈরি করে কিনা তা চেক করার প্রোগ্রাম

ধরি আমাদের একটি ২D ম্যাট্রিক্স আছে। আমাদের চেক করতে হবে কি কোনো সেল থেকে শুরু করে একই মানর অذیر সেলগুলোতে (আপ, ডাউন, লেফট, রাইট) ঘুরে ফিরে আসা যায়। আমরা একটি সেলকে দুবার ভিজিট করতে পারব না যা আমরা গত অবস্থায় ভিজিট کرده ছিলাম।

তাই, ইনপুট যদি নিচের ম্যাট্রিক্সের মত হয়, তবে আউটপুট হবে True, কারণ ২-গুলো ফলো করে একটি সাইকেল তৈরি করা যায়।

সমাধানের ধাপগুলো:

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