Min boards to cover roof holes

You are given an m x n binary grid roof representing a roof surface:

• roof[i][j] = 1 means the cell is intact.
• roof[i][j] = 0 means the cell is a hole that must be covered.

You can patch holes using wooden boards of two types:

1. A vertical board of size m x 1 that covers an entire column (all rows in that column).
2. A horizontal board of size 1 x n that covers an entire row (all columns in that row).

A board covers every cell it spans (intact or hole). You may place any number of boards.

Task: Return the minimum number of boards needed so that every hole cell (0) is covered by at least one placed board.

Example

roof = [
  [1,0,1],
  [0,1,1]
]

Holes are at (0,1) and (1,0). One optimal solution is: cover row 1 and column 2 (or other equivalents) with 2 boards.

Constraints (reasonable interview scale)

• 1 <= m, n <= 2000
• Total cells m*n can be large; aim for better than O((mn)^2) .

Note: This is a minimum-coverage question; your answer should be an integer minimum.