পাইথনে ২ডি গ্রিডে সাইকেল ডিটেকশন প্রোগ্রাম

মনে করুন grid নামক একটি ২ডি ক্যারেক্টার অ্যারে আছে যার সাইজ m x n। এতে সাইকেল আছে কিনা চেক করতে হবে। এখানে সাইকেল বলতে гриডে ৪ বা তার বেশি দৈর্ঘ্যের একটি পথ যেটা একই পজিশন থেকে শুরু ও শেষ হয়। আমরা চার দিকেই (আপ, ডাউন, লেফ্ট, রাইট) যেতে পারি যদি সেলের ভ্যালু বর্তমান সেলের সমান হয়, এবং একই সেল পুনরায় ভিজিট করতে পারব না।

যেমন, ইনপুট এমন হলে

আউটপুট হবে True, কারণ সবুজ সেলগুলো সাইকেল তৈরি করছে।

সমাধান পদ্ধতি

এই সমস্যাটি সমাধান করতে নিচের ধাপগুলো অনুসরণ করুন:

• WHITE := 0, GRAY := 1, BLACK := 2

• R := grid-এর রো কাউন্ট, C := grid-এর কলাম কাউন্ট

• color := ডিফল্ট ভ্যালু ০ olan একটি খালি ম্যাপ

• dfs() ফাংশন ডিফাইন করুন। এটি r, c, pr:=-1, pc:=-1 প্যারামিটার নেবে

  • color[r,c] := GRAY

  • di-এ থাকা প্রতিটি (x,y) জোড়ার জন্য

    • (nr,nc) := (r+x, c+y)

    • যদি 0 <= nr < R এবং 0 <= nc < C এবং grid[r][c] == grid[nr][nc] এবং (nr,nc) != (pr,pc) হয়, তবে

      • যদি color[nr,nc] == WHITE হয়, তবে

        • যদি dfs(nr,nc,r,c) true হয়, তবে True রিটার্ন করুন

      • অন্যথায় যদি color[nr,nc] == GRAY হয়, তবে

        • True রিটার্ন করুন

    • color[r,c] := BLACK

    • False রিটার্ন করুন

• মেইন মেথড থেকে:

• r = 0 থেকে R-1 পর্যন্ত

  • c = 0 থেকে C-1 পর্যন্ত

    • যদি color[r,c] == WHITE হয়, তবে

      • যদি dfs(r,c) true হয়, তবে True রিটার্ন করুন

• False রিটার্ন করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন আরও ভালো বোঝার জন্য:

from collections import defaultdict di = [(0,1),(1,0),(0,-1),(-1,0)] def solve(grid):    WHITE,GRAY,BLACK = 0 ,1 ,2    R,C = len(grid),len(grid[0])    color = defaultdict(int)    def dfs(r,c,pr=-1,pc=-1):       color[r,c] = GRAY       for x,y in di:          nr,nc = r+x,c+y          if (0<=nr
ইনপুট
7, [5,1,4,3]
আউটপুট
True