OI题库

【题目描述】

给出一个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