黑和白

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file blackandwhite.in Output file blackandwhite.out

【题目描述】

给出一个M行N列的网格,其中部分格子被染色。你将要计算在下面所述的约束下,填满网格剩余部分的方法总数:

网格中的每一个格子都应染成黑白二色之一。网格中所有的黑色格子应当四连通,所有的白色格子也应该四连通。在下面的两张图片中,只有右图是合法的。

另外,不能有全黑或全白的2*2子网格。在下面的两张图中,左边的图片中有2*2的全黑和全白网格,因此不合法,而由图中没有2*2的同色网格,因此是合法的。

不能改变已被染色格子的颜色。所有的格子都必须被染色。

【输入格式】

输入文件的第一行有2个正整数M,N,代表行数和列数

接下来的M行,每行有N个字符,它们代表了开始时M*N网格的状态。这些字符可能是如下三种:

#:一个被染成黑色的格子。

o:一个被染成白色的格子。

.:一个没有染色的格子。

【输出格式】

输出一行一个正整数,即染色方案总数。

【样例输入】

sample 1:


3 3

o..

.##

...



sample 2:


5 5

..#..

.....

....o

o....

.#...



sample 3:


7 5

.....

..o..

#....

.....

..o..

...#.

o....



sample 4:


2 3

###

oo#



sample 5:


6 8

........

........

........

........

.#......

........


【样例输出】

sample 1:

4


sample 2:

0


sample 3:

176


sample 4:

1


sample 5:

71582

【提示】

对于20%的数据,2<=M,N<=4

对于100%的数据,2<=M,N<=8

【来源】

Problemsetter: Jimmy Mårdell, Member of Elite Problemsetters' Panel

UVa10572 Black & White

刘汝佳,《算法竞赛入门经典训练指南》,P387 例题3