P5074 Eat the Trees

HDU1693: Eat the Trees

Given an $n \times m$ grid, some cells cannot be filled with lines, and all other cells must be filled. Multiple closed loops can be formed. Ask how many different ways there are to fill the grid?

Multiple test cases per input file. The first line contains a positive integer $T$, meaning there are $T$ test cases. For each test case: Line $1$: two integers $n, m\ (2 \le n, m \le 12)$. Lines $2$ to $n + 1$: each line contains $m$ digits ($1$ or $0$). $1$ means this cell must be filled with lines, and $0$ means this cell is not filled with lines.

For each test case, output one integer, representing the number of valid ways. It is guaranteed that the answer is less than $2^{63}$.

Translated by ChatGPT 5