โปรแกรมตรวจสอบองค์ประกอบบางอย่างในเมทริกซ์เป็นวัฏจักรหรือไม่อยู่ใน python

สมมุติว่าเรามีเมทริกซ์ 2 มิติ เราต้องตรวจสอบว่าเราสามารถเริ่มต้นจากบางเซลล์ได้หรือไม่ จากนั้นย้ายเซลล์ที่อยู่ติดกัน (ขึ้น ลง ซ้าย ขวา) ที่มีค่าเดียวกัน และกลับมายังจุดเริ่มต้นเดียวกัน เราไม่สามารถกลับไปดูเซลล์ที่เราเคยเยี่ยมชมครั้งล่าสุดได้

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

จากนั้นผลลัพธ์จะเป็น True เนื่องจากเราสามารถทำตาม 2s เพื่อสร้างวัฏจักร

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

• R :=จำนวนแถวของเมทริกซ์
• C :=จำนวนคอลัมน์ของเมทริกซ์
• vis :=สร้างเมทริกซ์ขนาด R x C และเติม False
• กำหนดฟังก์ชัน dfs() สิ่งนี้จะหยั่งราก
• stack :=สแต็คที่มีสององค์ประกอบ root และ null
• vis[root[0], root[1]] :=True
• ในขณะที่สแต็กไม่ว่างเปล่า ให้ทำ
  • [v, prev] :=องค์ประกอบด้านบนของสแต็กและป๊อปจากสแต็ก
  • สำหรับเพื่อนบ้าน w ของ v แต่ละคน ทำ
    • ถ้า w ไม่เหมือนกับก่อนหน้า แล้ว
      • ถ้า vis[w[0], w[1]] เป็นเท็จ แล้ว
        • vis[w[0], w[1]] :=จริง
        • ดัน [w, v] ลงในสแต็ก
    • มิฉะนั้น
      • คืนค่า True
• คืนค่าเท็จ
• จากวิธีหลัก ให้ทำดังนี้:
• สำหรับฉันในช่วง 0 ถึง R - 1 ทำ
  • สำหรับ j ในช่วง 0 ถึง C - 1 ทำ
    • ถ้า vis[i, j] เป็นเท็จ แล้ว
      • ถ้า dfs((i, j)) เป็นจริง ดังนั้น
        • คืนค่า True
• คืนค่าเท็จ

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

ตัวอย่าง

class Solution:
   def solve(self, matrix):
      R = len(matrix)
      C = len(matrix[0])

      def get_neighbors(i, j):
         val = matrix[i][j]
         for ii, jj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
            if 0 <= ii < R and 0 <= jj < C and matrix[ii][jj] == val:
               yield ii, jj

      vis = [[False] * C for _ in range(R)]

      def dfs(root):
         stack = [(root, None)]
         vis[root[0]][root[1]] = True
         while stack:
            v, prev = stack.pop()
            for w in get_neighbors(*v):
               if w != prev:
                  if not vis[w[0]][w[1]]:
                     vis[w[0]][w[1]] = True
                     stack.append((w, v))
                  else:
                     return True
         return False

      for i in range(R):
         for j in range(C):
            if not vis[i][j]:
               if dfs((i, j)):
                  return True
      return False
     
ob = Solution()
matrix = [
   [2, 2, 2, 1],
   [2, 1, 2, 1],
   [2, 2, 2, 1]
]
print(ob.solve(matrix))

อินพุต

[  
[2, 2, 2, 1],  
[2, 1, 2, 1],  
[2, 2, 2, 1] ]

ผลลัพธ์

True