3062 - 黑与白
给定一个包含M行和N列的部分填充网格，您需要计算有多少种方式在某种方式下填充网格的剩余部分，并输出其中一个方法（如果有的话）。
网格中的每个单元格都应该着色为黑色或白色。网格中的所有黑色单元格、网格中的所有白色单元格都应当互相连通（如果两个单元格上下左右相邻，那么视为两者之间有一条边）
下面显示了两个填充的网格，右边那个图满足连通的条件，左边那个不满足。
除此之外，在任意的2×2的子网格中不允许全是黑色或者全是白色。
左下图显示了一个由黑色和白色2×2块组成的网格，而右下图的网格不包含这样的2×2块
对于那些指定了颜色的网格，你不能修改它们，对于那么没有指定颜色的网格，你必须指定黑色/白色，不能不指定颜色
输入
输入中的第一行包含一个整数T（小于100）表示测试的样例数。
每个样例以两个整数N和M（2≤M，N≤8）开始，分别为行数和列数
接下来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