Chương trình kiểm tra các phần tử trong ma trận tạo thành chu trình (cycle) trong Python

Cho ma trận 2D. Kiểm tra có thể bắt đầu từ ô nào đó, di chuyển các ô liền kề (lên, xuống, trái, phải) cùng giá trị, và quay lại điểm xuất phát. Không được revisit ô vừa truy cập.

Ví dụ input:

Output: True (theo các ô giá trị 2 tạo thành chu trình).

Thuật toán DFS với stack:

• R, C = số hàng, cột
• vis = ma trận R×C đánh dấu đã thăm
• Hàm get_neighbors(i, j) trả về các ô liền kề cùng giá trị
• Hàm dfs(root) dùng stack: push (root, None), đánh dấu visited
• Khi pop (v, prev): duyệt neighbor w của v
  • Nếu w != prev và not vis[w]: mark visited, push (w, v)
  • Nếu w != prev và vis[w] → tìm thấy cycle → return True
• Duyệt toàn bộ ma trận, gọi dfs cho ô chưa thăm

Triển khai

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

Giải thích: Dùng DFS lặp (iterative) với stack lưu (current_node, parent_node). Phát hiện cycle khi gặp neighbor đã visited mà không phải parent. Phức tạp O(R×C).