Chương trình Python đếm số ô đất không thể thoát ra khỏi ma trận

Cho ma trận nhị phân: 1 là đất, 0 là nước. Từ ô đất có thể di chuyển lên/xuống/trái/phải (không chéo). Tìm số ô đất không thể đi ra ngoài biên ma trận.

Ví dụ

0 0 0 1
0 1 1 0
0 1 1 0
0 0 0 1

Output: 4 (4 ô đất ở giữa bị bao quanh bởi nước/biên).

Thuật toán (BFS từ biên)

1. Thu thập tất cả ô đất nằm trên biên ma trận vào hàng đợi q.
2. Đánh dấu các ô này đã thăm (gán 0).
3. BFS: lấy từng ô từ q, kiểm tra 4 hướng. Nếu ô lân cận là đất (1) và trong phạm vi → gán 0 và thêm vào q.
4. Sau BFS, các ô đất còn lại (1) chính là những ô không thể thoát ra biên. Trả về tổng các ô còn lại.

Mã nguồn Python

def solve(matrix):
    # Khởi tạo hàng đợi với các ô đất trên biên
    q = [(i, j) for i in range(len(matrix))
                  for j in range(len(matrix[i]))
                  if matrix[i][j] and (i == 0 or i == len(matrix)-1
                                       or j == 0 or j == len(matrix[i])-1)]

    idx = 0
    # Đánh dấu ô đất trên biên đã thăm
    for x, y in q:
        matrix[x][y] = 0

    # BFS lan truyền từ biên vào trong
    while idx < len(q):
        x, y = q[idx]
        for dx, dy in [(-1, 0), (0, -1), (0, 1), (1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[nx]) and matrix[nx][ny]:
                matrix[nx][ny] = 0
                q.append((nx, ny))
        idx += 1

    # Tổng các ô đất còn lại = ô không thể thoát ra biên
    return sum(sum(row) for row in matrix)

# Test
matrix = [
    [0, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 1]
]
print(solve(matrix))  # Output: 4

Độ phức tạp

• Thời gian: O(m*n) — mỗi ô được thăm tối đa 1 lần.
• Không gian: O(m*n) cho hàng đợi (worst case toàn bộ ma trận là đất).