पायथन में 2डी ग्रिड में चक्रों का पता लगाने का कार्यक्रम

मान लीजिए कि हमारे पास वर्णों की एक 2D सरणी है, जिसे m x n आकार का ग्रिड कहा जाता है। हमें यह जांचना होगा कि हम इसके अंदर एक चक्र का पता लगा सकते हैं या नहीं। यहां एक चक्र ग्रिड में लंबाई 4 या अधिक का पथ है जो एक ही स्थिति में शुरू और समाप्त होता है। हम चार दिशाओं (ऊपर, नीचे, बाएँ, या दाएँ) में जा सकते हैं, यदि इसका वर्तमान सेल का मान समान है, और हम किसी सेल पर दोबारा नहीं जा सकते।

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

तो आउटपुट सही होगा, क्योंकि हरे रंग की कोशिकाएं चक्र बना रही हैं।

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

• सफेद:=0, ग्रे:=1, काला:=2

• आर:=ग्रिड की पंक्ति गणना

• सी :=ग्रिड की कॉलम संख्या

• रंग :=एक खाली नक्शा, जिसका डिफ़ॉल्ट मान 0

  . है

• फ़ंक्शन को परिभाषित करें dfs() । इसमें r, c, pr:=-1,pc:=-1

  लगेगा

• रंग [आर, सी]:=ग्रे

• di में प्रत्येक जोड़ी (x,y) के लिए, do

  • (एनआर,एनसी) :=(आर+एक्स,सी+वाई)

  • अगर 0 <=एनआर <आर और 0 <=एनसी <सी और ग्रिड [आर, सी] ग्रिड के समान है [एनआर, एनसी] और (एनआर, एनसी) (पीआर, पीसी) के समान नहीं है, तो

    • अगर रंग [एनआर, एनसी] सफेद के समान है, तो

      • अगर dfs(nr,nc,r,c) सत्य है, तो

        • सही लौटें

      • अन्यथा जब color[nr,nc] GRAY के समान हो, तब

        • सही लौटें

    • रंग [आर, सी]:=काला

    • झूठी वापसी

    • मुख्य विधि से, निम्न कार्य करें

    • r के लिए 0 से R-1 की सीमा में, करें

      • सी के लिए 0 से सी -1 की सीमा में, करो

        • अगर रंग [आर, सी] सफेद के समान है, तो

          • अगर 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