背景

ural 1519

陈丹琦《基于连通性状态压缩的动态规划问题》中的例题。

题目描述

给出 $n\times m$ 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？

输入格式

第一行，两个整数，分别代表 $n,m$。

从第二行到第 $(n+1)$ 行，每行有一个长度为 $m$ 的只含 * 和 . 的字符串，* 表不能铺线，. 表必须铺。

输出格式

输出一行一个整数，表示总方案数。

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

2

4 4
....
....
....
....

6

提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 $2\le n,m\le 12$。