3062 - 黑与白

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 5 秒

内存限制 : 1024 MB

给定一个包含M行和N列的部分填充网格，您需要计算有多少种方式在某种方式下填充网格的剩余部分，并输出其中一个方法（如果有的话）。

网格中的每个单元格都应该着色为黑色或白色。网格中的所有黑色单元格、网格中的所有白色单元格都应当互相连通（如果两个单元格上下左右相邻，那么视为两者之间有一条边）

下面显示了两个填充的网格，右边那个图满足连通的条件，左边那个不满足。

除此之外，在任意的2×2的子网格中不允许全是黑色或者全是白色。

左下图显示了一个由黑色和白色2×2块组成的网格，而右下图的网格不包含这样的2×2块

对于那些指定了颜色的网格，你不能修改它们，对于那么没有指定颜色的网格，你必须指定黑色/白色，不能不指定颜色

输入

输入中的第一行包含一个整数 $T（小于100）$ 表示测试的样例数。

每个样例以两个整数N和M（ $2\leqM，N\leq8$ ）开始，分别为行数和列数

接下来N行，每行M个字符表示网格

'#' - 网格被指定为黑色

'o' - 网格被指定为白色

'.' - 尚未指定颜色的单元格

输出

第一行输出一个数字，表示允许的方案数

如果方案数大于0，则再输出N行M列。输出任意一种满足规则的答案。

在不同测试数据之间额外多输出一行空格。

样例

输入

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

输出

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

来源

UVa10572