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

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

इसलिए, यदि इनपुट इस तरह है

m	m	m	p
m	k	m	m
m	m	s	m
f	t	m	m

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

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

WHITE := 0, GRAY := 1, BLACK := 2
R := grid की पंक्ति संख्या
C := grid की स्तंभ संख्या
color := एक खाली मैप, जिसका डिफ़ॉल्ट मान 0 है
एक फ़ंक्शन 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 वापस करें
  - अन्यथा जब 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 वापस करें
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 < 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