Chương trình kiểm tra một số phần tử trong ma trận có tạo thành chu trình hay không trong python

Giả sử chúng ta có một ma trận 2d. Chúng ta phải kiểm tra xem chúng ta có thể bắt đầu từ một ô nào đó, sau đó di chuyển các ô liền kề (lên, xuống, trái, phải) có cùng giá trị và quay lại cùng điểm bắt đầu hay không. Chúng tôi không thể truy cập lại ô mà chúng tôi đã truy cập lần trước.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là True, vì chúng ta có thể làm theo 2 giây để tạo thành một chu kỳ.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• R:=số hàng của ma trận
• C:=số cột của ma trận
• vis:=tạo một ma trận có kích thước R x C và điền vào False
• Định nghĩa một hàm dfs (). Điều này sẽ bén rễ
• stack:=một ngăn xếp có hai phần tử gốc và null
• vis [root [0], root [1]]:=True
• trong khi ngăn xếp không trống, hãy thực hiện
  • [v, prev]:=phần tử trên cùng của ngăn xếp và bật ra từ ngăn xếp
  • đối với mỗi người hàng xóm w của v, thực hiện
    • nếu w không giống như trước, thì
      • nếu vis [w [0], w [1]] là false thì
        • vis [w [0], w [1]]:=True
        • đẩy [w, v] vào ngăn xếp
    • nếu không,
      • trả về True
• trả về Sai
• Từ phương thức chính, hãy làm như sau:
• đối với tôi trong phạm vi từ 0 đến R - 1, thực hiện
  • đối với j trong phạm vi từ 0 đến C - 1, thực hiện
    • nếu vis [i, j] là false, thì
      • nếu dfs ((i, j)) là true, thì
        • trả về True
• trả về Sai

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

True