โปรแกรมตรวจจับวัฏจักรในกริด 2D ใน Python

สมมติว่าเรามีอาร์เรย์ 2D ของตัวอักษรชื่อ grid ขนาด m x n เราต้องตรวจสอบว่าสามารถตรวจจับวัฏจักรภายในได้หรือไม่ วัฏจักรคือเส้นทางยาว 4 หรือมากกว่าในกริดที่เริ่มและจบที่ตำแหน่งเดียวกัน เราสามารถเคลื่อนที่ได้ 4 ทิศทาง (บน, ล่าง, ซ้าย, ขวา) ถ้ามีค่าเท่ากับเซลล์ปัจจุบัน และไม่สามารถไปเยี่ยมเซลล์เดิมซ้ำได้

เช่น ถ้าอินพุตเป็นตารางดังภาพ (เซลล์สีเขียว) ผลลัพธ์จะเป็น True เพราะเซลล์สีเขียวสร้างวัฏจักร

วิธีแก้ปัญหา

• WHITE := 0, GRAY := 1, BLACK := 2
• R := จำนวนแถวของ grid, C := จำนวนคอลัมน์ของ grid
• color := แมปว่าง ค่าเริ่มต้น 0
• กำหนดฟังก์ชัน dfs() รับ r, c, pr := -1, pc := -1:
  • color[r,c] := GRAY
  • สำหรับแต่ละคู่ (x,y) ใน di:
    • (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: return True
      • มิฉะนั้นถ้า color[nr,nc] เท่ากับ GRAY: return True
  • color[r,c] := BLACK
  • return False
• จากเมธอดหลัก:
  • สำหรับ r ในช่วง 0 ถึง R - 1:
    • สำหรับ c ในช่วง 0 ถึง C - 1:
      • ถ้า color[r,c] เท่ากับ WHITE:
        • ถ้า dfs(r,c) เป็น true: return True
  • return 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