Chương trình đếm ô an toàn khi bom nổ trong ma trận Python

Cho ma trận nhị phân 2D: 1 = bom, 0 = ô trống. Khi bom nổ, toàn bộ hàng và cột chứa bom bị phá hủy. Tìm số ô an toàn (không nằm trên hàng/cột nào có bom).

Ví dụ

Ma trận:

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

Hàng 0 và cột 0,1 có bom → ô an toàn: (1,2) và (2,2) → kết quả: 2.

Thuật toán

1. Tạo mảng row_has_bomb kích thước số hàng, col_has_bomb kích thước số cột, khởi tạo False.
2. Duyệt ma trận: nếu matrix[i][j] == 1 → row_has_bomb[i] = True, col_has_bomb[j] = True.
3. Đếm số ô (i,j) mà row_has_bomb[i] == False VÀ col_has_bomb[j] == False.

Triển khai Python

class Solution:
    def solve(self, matrix):
        if not matrix:
            return 0
        rows = len(matrix)
        cols = len(matrix[0])
        
        row_has_bomb = [False] * rows
        col_has_bomb = [False] * cols
        
        # Đánh dấu hàng/cột có bom
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == 1:
                    row_has_bomb[i] = True
                    col_has_bomb[j] = True
        
        # Đếm ô an toàn
        safe = 0
        for i in range(rows):
            for j in range(cols):
                if not row_has_bomb[i] and not col_has_bomb[j]:
                    safe += 1
        return safe

# Test
ob = Solution()
matrix = [[1,1,0], [0,0,0], [0,0,0]]
print(ob.solve(matrix))  # Output: 2

Độ phức tạp

• Thời gian: O(m × n).
• Không gian: O(m + n).