পাইথনে 2D গ্রিডে চক্র সনাক্ত করার প্রোগ্রাম

ধরুন আমাদের কাছে একটি 2D অক্ষর রয়েছে যাকে বলা হয় m x n আকারের গ্রিড। আমরা এর ভিতরে একটি চক্র সনাক্ত করতে পারি কি না তা পরীক্ষা করতে হবে। এখানে একটি চক্র হল গ্রিডে 4 বা তার বেশি দৈর্ঘ্যের একটি পথ যা একই অবস্থানে শুরু এবং শেষ হয়। আমরা চারটি দিকে (উপর, নিচে, বাম বা ডানে) যেতে পারি, যদি এটির বর্তমান কক্ষের মান একই থাকে এবং আমরা কিছু কক্ষ পুনরায় দেখতে পারি না।

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

তাহলে আউটপুট হবে True, কারণ সবুজ কোষ চক্র গঠন করছে।

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

• সাদা :=0, ধূসর :=1, কালো :=2

• R :=গ্রিডের সারি গণনা

• C :=গ্রিডের কলাম সংখ্যা

• রঙ :=একটি খালি মানচিত্র, যার ডিফল্ট মান হল 0

• একটি ফাংশন dfs() সংজ্ঞায়িত করুন। এটি r, c, pr:=-1,pc:=-1

  লাগবে

• রঙ[r,c] :=ধূসর

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

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

  • যদি 0 <=nr

    • যদি রঙ [nr,nc] সাদার মতো হয়, তাহলে

      • যদি dfs(nr,nc,r,c) সত্য হয়, তাহলে

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

      • অন্যথায় যখন রঙ [nr,nc] ধূসর এর মত হয়, তখন

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

    • রঙ[r,c] :=কালো

    • রিটার্ন ফলস

    • প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন

    • 0 থেকে R - 1 রেঞ্জের r-এর জন্য, করুন

      • 0 থেকে C - 1 পরিসরে c এর জন্য, করুন

        • যদি রঙ[r,c] সাদার মতো হয়, তাহলে

          • যদি dfs(r,c) সত্য হয়, তাহলে

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

• রিটার্ন ফলস

উদাহরণ

আসুন আরও ভালভাবে বোঝার জন্য নিম্নলিখিত বাস্তবায়ন দেখি

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<R and 0<=nc<C and grid[r][c] == grid[nr][nc] and (nr,nc)!=(pr,pc)):
            if color[nr,nc]==WHITE:
               if dfs(nr,nc,r,c):
                  return True
            elif color[nr,nc] == GRAY:
               return True

      color[r,c] = BLACK
      return False

   for r in range(R):
      for c in range(C):
         if color[r,c] == WHITE:
            if dfs(r,c):
               return True
   return False
matrix = [["m","m","m","p"],["m","k","m","m"],["m","m","s","m"],["f","m","m","m"]]
print(solve(matrix))

ইনপুট

7, [5,1,4,3]

আউটপুট

True