Black & White

题意翻译

题目大意 一个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”表示白格，“.”表示尚未涂色的格子。 输出格式 对于每组数据，第一行输出方案总数，如果存在一组方案，接下来是任意一组方案。在每组数据之间输出一行空行。

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=17&page=show_problem&problem=1513 [PDF](https://uva.onlinejudge.org/external/105/p10572.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10572/f03240f6ef7e3c665608a49c5ad0d6db27809c53.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10572/3a6f7eb38401667ae31fe5213d958909932cd0fd.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA10572/e0517b17724262fc72fb8eacab76d372dc88df71.png)

输入输出样例

输入样例 #1

5
3 3
o..
.##
...
5 5
..#..
.....
....o
o....
.#...
7 5
.....
..o..
#....
.....
..o..
...#.
o....
2 3
###
oo#
6 8
........
........
........
........
.#......
........

输出样例 #1

4
oo#
o##
oo#
0
176
#####
#ooo#
###oo
#o##o
#oooo
####o
ooooo
1
###
oo#
71582
#ooooooo
#o#####o
#ooooo#o
#o#o#o#o
#######o
#ooooooo