Bài 23.5. An Ninh Thành Phố - [Độ khó: Khá]

Thị trưởng thành phố muốn triển khai một hệ thống an ninh giám sát mới. Thành phố được quy hoạch thành một lưới ô vuông \(N \times M\). Một số ô là đất trống, một số ô đã được lắp đặt camera, và một số ô là các tòa nhà không thể đặt camera cũng như không cần giám sát.

Một camera đặt tại ô \((r, c)\) có khả năng giám sát tất cả các ô trong cùng hàng \(r\) và cùng cột \(c\). Các ô là tòa nhà (có giá trị -1) không thể được giám sát bởi camera, ngay cả khi chúng nằm trên cùng hàng hoặc cột với một camera.

Nhiệm vụ của bạn là tính toán số lượng ô đất trống (có giá trị 0) mà không được giám sát bởi bất kỳ camera nào.

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(M\) (\(1 \le N, M \le 100\)), lần lượt là số hàng và số cột của bản đồ thành phố. \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên \(T_{i,j}\) (\(T_{i,j} \in \{-1, 0, 1\}\)), biểu thị trạng thái của ô \((i,j)\):

• \(T_{i,j} = -1\): Ô là tòa nhà.
• \(T_{i,j} = 0\): Ô đất trống.
• \(T_{i,j} = 1\): Ô có một camera.

OUTPUT FORMAT

Một số nguyên duy nhất là số lượng ô đất trống không được giám sát.

Ví dụ:

Input:

4 4
0 0 1 0
0 -1 0 0
1 0 0 -1
0 0 0 0

Output:

3

Giải thích: Bản đồ:

0 0 1 0
0 -1 0 0
1 0 0 -1
0 0 0 0

• Camera tại (0,2):
  • Giám sát hàng 0: (0,0), (0,1), (0,2), (0,3)
  • Giám sát cột 2: (0,2), (1,2), (2,2), (3,2)
• Camera tại (2,0):
  • Giám sát hàng 2: (2,0), (2,1), (2,2), (2,3)
  • Giám sát cột 0: (0,0), (1,0), (2,0), (3,0)

Các ô bị giám sát (là 0 hoặc 1):

• Hàng 0: (0,0), (0,1), (0,2), (0,3)
• Hàng 2: (2,0), (2,1), (2,2), (2,3)
• Cột 0: (0,0), (1,0), (2,0), (3,0)
• Cột 2: (0,2), (1,2), (2,2), (3,2)

Ghi nhận các ô là tòa nhà (-1) không bị giám sát:

• Tòa nhà tại (1,1) và (2,3) không bao giờ được giám sát.

Các ô đất trống ban đầu (có giá trị 0): (0,0), (0,1), (0,3) (1,0), (1,2), (1,3) (2,1), (2,2) (3,0), (3,1), (3,2), (3,3)

Các ô đất trống ĐƯỢC GIÁM SÁT:

• (0,0), (0,1), (0,3) (do camera ở (0,2) và (2,0))
• (1,0) (do camera ở (2,0))
• (1,2) (do camera ở (0,2))
• (2,1), (2,2) (do camera ở (2,0) và (0,2))
• (3,0) (do camera ở (2,0))
• (3,2) (do camera ở (0,2))

Các ô đất trống KHÔNG ĐƯỢC GIÁM SÁT:

• (1,3)
• (3,1)
• (3,3) Tổng cộng có 3 ô đất trống không được giám sát.