Chương trình đếm phần tử ma trận thỏa mãn điều kiện hàng/cột trong Python

Cho ma trận nhị phân. Đếm số phần tử thỏa mãn:

• matrix[r][c] = 1
• Trên hàng r: chỉ có duy nhất 1 tại cột c (các cột khác = 0)
• Trên cột c: chỉ có duy nhất 1 tại hàng r (các hàng khác = 0)

Ví dụ: ma trận 3×3 với 1 tại (0,2), (1,0), (2,1) → kết quả 3.

Thuật toán giải quyết (O(m×n))

1. Tính tổng từng hàng: row[r] = sum(matrix[r])
2. Tính tổng từng cột: col[c] = sum(matrix[r][c] for r)
3. Duyệt mọi ô: nếu matrix[r][c] == 1 and row[r] == 1 and col[c] == 1 thì đếm++
4. Trả về kết quả

Ví dụ minh họa

def solve(matrix):
    if not matrix:
        return 0
    row = [sum(r) for r in matrix]
    col = [sum(c) for c in zip(*matrix)]
    m, n = len(matrix), len(matrix[0])
    res = 0
    for r in range(m):
        for c in range(n):
            if matrix[r][c] == 1 and row[r] == 1 and col[c] == 1:
                res += 1
    return res

matrix = [[0, 0, 1], [1, 0, 0], [0, 1, 0]]
print(solve(matrix))

Đầu vào

[[0, 0, 1],[1, 0, 0],[0, 1, 0]]

Đầu ra

3