解题思路

主要思路：

1. 状态表示：使用二维布尔数组表示网格状态，True表示该位置被积木覆盖

2. 积木类型：生成所有可能的1×3（横向）和3×1（纵向）积木位置

3. 放置规则检查

题目内容

小钟在一张长为$n$、宽为$m$的网格图上摆放积木。图上有一些格子是特殊格子，小钟有无限个尺寸为$1×3$或$3×1$的积木。每次小钟摆放积木时，需要满足以下条件:积木至少有一端与特殊格子重合，只能在网格图内摆放，不能越界，且当前要摆放的积木不能与已经摆放的积木发生重叠。小钟会一直按上述要求摆放积木，直到无法再摆放积木为止。

小爱在一旁看着小钟摆放积木，她很好奇网格图最终一共有多少种可能的局面。两种局面不同，当且仅当网格图中存在某个格子，一种局面中该格子被积木覆盖，另一种局面中没有被覆盖。请你计算网格图最终有多少可能的局面。注意，局面的不同与如何摆放无关，仅与格子是否被覆盖有关系!

$1≤n,m≤8$。保证特殊格子的数量不超过$13$，数据随机生成。

输入描述

第一行有两个整数$n(1≤n≤8)、m(1≤m≤8)$，分别表示网格图的长和宽.

接下来$n$行每行输入$m$个字符，若网格图第$i$行第$j$列位置是特殊格子，则第$i$行第$j$个字符为"*",否则为"."。

输出描述

输出一个整数，表示网格图最终可能的局面个数。

样例1

输入

4 4
....
...*
.*..
....

输出

2

说明

对于第一个样例，两种可能的游戏结束局面如下: . * . .

. * . *

. * . *

. . . *

. . . .

. * * *

. * * *

. . . .

样例2

输入

3 3
***
***
***

输出

1

说明

对于第二个样例，可以横着摆三行每行一个积木，也可以纵着摆三列每列一个积木，但是这两种方式所导致的最终的局面是相同的，因此可能的局面数是$1$。