Freaks City

Given an $n \times m$ grid where each cell is either empty (.) or blocked (*), place the minimum number of $1 \times 2$ or $2 \times 1$ dominoes such that no two adjacent empty cells remain — i.e., it's impossible to place any additional domino. Constraints: $1 \leq n \leq 70$, $1 \leq m \leq 7$. Due to the small value of $m$, a dynamic program ...