题面翻译

题目大意

一个m×n的网格，有的格子已经染上黑色或白色，现在要求将所有的未染色格子染上黑色或白色，使得满足以下2个限制：

1. 所有的黑色的格子是四连通的，所有的白色格子也是四连通的。

2. 不会有一个2×2的子矩阵的4个格子的颜色全部相同。

如图1，3不合法，图2，4合法。

求方案总数和其中一组方案。(m, n ≤ 8) 输入格式

输入第一行为数据组数T（T≤100）。每组数据第一行为两个整数m和n（2≤n，m≤8）。以下m行每行包含n个字符，“#”表示黑格，“o”表示白格，“.”表示尚未涂色的格子。 输出格式

对于每组数据，第一行输出方案总数.

题目描述

PDF

输入格式

输出格式

样例 #1

样例输入 #1

1
3 3
o..
.##
...

样例输出 #1

4