UVA10572 Black & White

题目大意 一个 $m×n$ 的网格，有的格子已经染上黑色或白色，现在要求将所有的未染色格子染上黑色或白色，使得满足以下两个限制： 1) 所有的黑色的格子是四连通的，所有的白色格子也是四连通的。 2) 不会有一个 2×2 的子矩阵的 4 个格子的颜色全部相同。 如图 1，3 不合法，图 2，4 合法。  求方案总数和其中一组方案。

输入第一行为数据组数 $T(T\le 100)$。每组数据第一行为两个整数 $m$ 和 $n(2\le m,n\le 8)$。以下 $m$ 行每行包含 $n$ 个字符，`#` 表示黑格，`o` 表示白格，`.` 表示尚未涂色的格子。

对于每组数据，第一行输出方案总数，如果存在一组方案，接下来是任意一组方案。在每组数据之间输出一行空行。