โปรแกรมตรวจจับวงจรในตาราง 2 มิติใน Python

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

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น True เพราะเซลล์สีเขียวกำลังสร้างวงจร

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สีขาว :=0, สีเทา :=1, สีดำ :=2

• R :=จำนวนแถวของกริด

• C :=จำนวนคอลัมน์ของกริด

• color :=แผนที่ว่างซึ่งมีค่าเริ่มต้นคือ 0

• กำหนดฟังก์ชัน dfs() นี่จะใช้เวลา r, c, pr:=-1,pc:=-1

• color[r,c] :=สีเทา

• สำหรับแต่ละคู่ (x,y) ใน di ทำ

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

  • ถ้า 0 <=nr

    • ถ้า color[nr,nc] เหมือนกับ WHITE แล้ว

      • ถ้า dfs(nr,nc,r,c) เป็นจริง ดังนั้น

        • คืนค่า True

      • มิฉะนั้น เมื่อ color[nr,nc] เหมือนกับ GREY แล้ว

        • คืนค่า True

    • color[r,c] :=สีดำ

    • คืนค่าเท็จ

    • จากวิธีหลัก ให้ทำดังนี้

    • สำหรับ r ในช่วง 0 ถึง R - 1 ให้ทำ

      • สำหรับ c ในช่วง 0 ถึง C - 1 ทำ

        • ถ้า color[r,c] เหมือนกับ WHITE แล้ว

          • ถ้า dfs(r,c) เป็นจริง

            • คืนค่า True

• คืนค่าเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

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